算法【完全背包】

完全背包与01背包的区别仅在于每种商品可以选取无限次。时间复杂度O(物品数量 * 背包容量)

下面通过题目加深理解。

题目一

测试链接：疯狂的采药 - 洛谷

分析：这是一道完全背包的模板题。对于第i个物品的可能性展开也有两种，第一种是不取第i个物品，即就是从0到i-1个物品里面取剩余重量为j的最大价值；第二种是只取一个第i个物品，即从0到i个物品取剩余重量为j-一个i物品重量的最大值+一个i物品的价值。下面代码直接采用空间压缩的方法，对于此种相当标准的完全背包，应该记住其空间压缩的解法，对于一些带有完全背包性质的题，可以使用记忆化搜索，再改为严格位置依赖以及空间压缩等。因为题目有个测试答案超过int，所以为了通过dp用了指针，一般是直接定义dp为静态数组。代码如下。

#include <iostream>
using namespace std;
int t, m;
int herb[10001][2];
long long* dp; 
int main(void){scanf("%d%d", &t, &m);for(int i = 0;i < m;++i){scanf("%d%d", &herb[i][0], &herb[i][1]);}int length = (10000000 / m) + 2;dp = new long long [length];for(int i = 0;i < length;++i){dp[i] = 0;}for(int i = 0;i < m;++i){for(int j = 0;j <= t;++j){if(j - herb[i][0] >= 0){dp[j] = dp[j] > dp[j-herb[i][0]] + herb[i][1] ?dp[j] : dp[j-herb[i][0]] + herb[i][1];}}}printf("%ld", dp[t]);delete [] dp;return 0;
}

其中，dp数组表示在前i个物品里面取，剩余重量为j的情况下的最大价值。

题目二

测试链接：10. 正则表达式匹配 - 力扣（LeetCode）

分析：这道题需要注意可能性的展开。对于字符串s到了末尾而字符串p也到了末尾，则代表匹配成功；如果字符串s到了末尾且字符串p剩余的后缀能够成为一个空串也代表能够匹配成功；而字符串s没到末尾但字符串p到了末尾，代表匹配不成功。因为存在*的特殊情况，所以需要对下一位置是否为*分情况讨论。下一个位置不是*时，如果当前两个字符串的字符能够匹配成功，则整个字符串是否匹配成功取决于后一位置的字符匹配；如果匹配不成功，则不论后一位置匹配能否成功，都是不成功的。如果下一位置为*则具有完全背包性质，可以不取即直接跳过当前位置和当前位置之后的*，从*之后的位置开始匹配；或者如果当前位置能够匹配成功，则可多次使用当前位置与下一位置的*进行匹配。下面代码为记忆化搜索版本。代码如下。

class Solution {
public:int dp[20][20];int f(int index1, int index2, string s, string p){if(index1 == s.size()){if(index2 == p.size()){return 1;}else{return index2 + 1 < p.size() && p[index2+1] == '*' && f(index1, index2+2, s, p);}}if(index2 == p.size()){return 0;}if(dp[index1][index2] != -1){return dp[index1][index2];}char ch1 = s[index1];char ch2 = p[index2];int ans;if((index2+1 < p.size() && p[index2+1] != '*') || index2+1 == p.size()){if(ch1 != ch2 && ch2 != '.'){ans = 0;}else{ans = f(index1+1, index2+1, s, p);}}else{ans = f(index1, index2+2, s, p);if(ch1 == ch2 || ch2 == '.'){ans |= f(index1+1, index2, s, p);}}dp[index1][index2] = ans;return ans;}void build(){for(int i = 0;i < 20;++i){for(int j = 0;j < 20;++j){dp[i][j] = -1;}}}bool isMatch(string s, string p) {build();return f(0, 0, s, p);}
};

其中，f方法表示在以字符串s的index1下标开始，字符串p的index2的下标开始匹配的情况下，返回能否匹配成功。这里不用bool类型是因为，dp需要1表示成功，0表示失败，-1表示未赋值。

题目三

测试链接：44. 通配符匹配 - 力扣（LeetCode）

分析：这道题和上一道题类似，不过可能性少了许多。对于字符是否是*分情况讨论，如果不是*且当前字符能够匹配成功，则整个字符串能否匹配成功取决于后一位置的字符匹配；如果当前位置为*，则可以不要这个*，即从下一位置开始匹配或者重复使用多次这个*即匹配一个字符序列。需要注意的是下面的代码分别是记忆化搜索、严格位置依赖、空间压缩的版本，并且记忆化搜索会超时。代码如下。

class Solution {
public:int dp[2000][2000];void build(){for(int i = 0;i < 2000;++i){for(int j = 0;j < 2000;++j){dp[i][j] = -1;}}}int f(int index1, int index2, string s, string p){if(index1 == s.size()){if(index2 == p.size()){return 1;}else{return p[index2] == '*' && f(index1, index2+1, s, p);}}if(index2 == p.size()){return 0;}if(dp[index1][index2] != -1){return dp[index1][index2];}char ch1 = s[index1];char ch2 = p[index2];int ans;if(ch2 != '*'){ans = (ch1 == ch2 || ch2 == '?') && f(index1+1, index2+1, s, p);}else{ans = f(index1, index2+1, s, p);ans |= f(index1+1, index2, s, p);}dp[index1][index2] = ans;return ans;}bool isMatch(string s, string p) {build();return f(0, 0, s, p);}
};

其中，f方法表示在以字符串s的index1下标开始，字符串p的index2的下标开始匹配的情况下，返回能否匹配成功。

class Solution {
public:bool dp[2001][2001];bool isMatch(string s, string p) {int length1 = s.size();int length2 = p.size();dp[length1][length2] = true;for(int index2 = length2-1;index2 >= 0;--index2){dp[length1][index2] = p[index2] == '*' && dp[length1][index2+1];}for(int index1 = length1-1;index1 >= 0;--index1){dp[index1][length2] = false;}for(int i = length1-1;i >= 0;--i){for(int j = length2-1;j >= 0;--j){if(p[j] != '*'){dp[i][j] = (s[i] == p[j] || p[j] == '?') && dp[i+1][j+1];}else{dp[i][j] = dp[i][j+1] || dp[i+1][j];}}}return dp[0][0];}
};

其中，dp数组的初始化参考记忆化搜索时递归的出口条件；dp数组的含义和记忆化搜索的f方法含义一样。

class Solution {
public:bool dp[2001];bool isMatch(string s, string p) {int length1 = s.size();int length2 = p.size();bool temp1, temp2;dp[length2] = true;for(int index2 = length2-1;index2 >= 0;--index2){dp[index2] = p[index2] == '*' && dp[index2+1];}for(int i = length1-1;i >= 0;--i){temp1 = i == length1-1 ? true : false;dp[length2] = false;for(int j = length2-1;j >= 0;--j){temp2 = dp[j];if(p[j] != '*'){dp[j] = (s[i] == p[j] || p[j] == '?') && temp1;}else{dp[j] = dp[j+1] || dp[j];}temp1 = temp2;}}return dp[0];}
};

对于这道题的空间压缩需要使用到辅助变量存储一些值。

题目四

测试链接：[USACO08NOV] Buying Hay S - 洛谷

分析：对于这道题，主要思路是使用二分答案法得到每次的开销，对于得到的开销求出采购到的最大甘草磅数能否满足题目条件，根据能否满足条件进行二分，继续求得开销（二分答案法详情见拙作 算法【二分答案法】）。代码如下。

#include <iostream>
#include <vector>
using namespace std;
int N, H;
int firm[100][2];
vector<int> dp;
bool f(int cost){dp.assign(cost+1, 0);for(int i = 0;i < N;++i){for(int j = 0;j <= cost;++j){if(j - firm[i][1] >= 0){dp[j] = dp[j] > dp[j-firm[i][1]] + firm[i][0] ?dp[j] : dp[j-firm[i][1]] + firm[i][0];}}}return dp[cost] >= H;
}
int main(void){int max_cost = 0;int ans;scanf("%d%d", &N, &H);for(int i = 0;i < N;++i){scanf("%d%d", &firm[i][0], &firm[i][1]);max_cost = max_cost > ((H + firm[i][0] - 1)/firm[i][0]) * firm[i][1] ?max_cost : ((H + firm[i][0] - 1)/firm[i][0]) * firm[i][1];}int left = 0, right = max_cost, middle;while (left <= right){middle = left + (right - left) / 2;if(f(middle)){ans = middle;right = middle - 1;}else{left = middle + 1;}}printf("%d", ans);return 0;
}