网站空间运行挂机宝,广东建设厅网站,一个新网站做多久才有流量转化,WordPress禁止多ip完全背包与01背包的区别仅在于每种商品可以选取无限次。时间复杂度O(物品数量 * 背包容量)
下面通过题目加深理解。 题目一
测试链接#xff1a;疯狂的采药 - 洛谷
分析#xff1a;这是一道完全背包的模板题。对于第i个物品的可能性展开也有两种#xff0c;第一种是不取第…完全背包与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[index21] * f(index1, index22, 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((index21 p.size() p[index21] ! *) || index21 p.size()){if(ch1 ! ch2 ch2 ! .){ans 0;}else{ans f(index11, index21, s, p);}}else{ans f(index1, index22, s, p);if(ch1 ch2 || ch2 .){ans | f(index11, 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, index21, 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(index11, index21, s, p);}else{ans f(index1, index21, s, p);ans | f(index11, 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][index21];}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[i1][j1];}else{dp[i][j] dp[i][j1] || dp[i1][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[index21];}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[j1] || 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];
vectorint dp;
bool f(int cost){dp.assign(cost1, 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;
}
