微网站自己怎么做,网站设计定做,资讯网站 怎么做,phpcms模板01背包
代码 背包问题的滚动数组优化版本建议在完全弄懂了普通的二维01背包问题后再进行食用#xff0c;不然会出现消化不良的症状… 我们可以将背包问题中DP数组的下标看作成两个集合 下面对比两种不同实现方法的区别#xff1a; 朴素二维DP版本 使用dp[不超过i的物品集合]…01背包
代码 背包问题的滚动数组优化版本建议在完全弄懂了普通的二维01背包问题后再进行食用不然会出现消化不良的症状… 我们可以将背包问题中DP数组的下标看作成两个集合 下面对比两种不同实现方法的区别 朴素二维DP版本 使用dp[不超过i的物品集合][不超过j的背包集合]。我们会发现每次使用的[不超过第i个物品的集合]只会是i和i-1再往前的集合在后续的计算都不会被使用所以可以采用滚动数组的思想不断的更新一个一维数组来达到相同的目的。同时我们每次会对每一个物品寻找所有[不超过j的背包的集合]如果背包放不下这个物品直接继承没有放i物品的状态即可也就是[不超过i-1位物品]的集合。同时这里和优化版本的区别还在于遍历顺序朴素版本不用考虑遍历顺序但是优化版本需要注意。 #include iostream
using namespace std;
// DP-normal-wayconst int N 1010;
int n, m; //n件物品 m容量的背包
int v[N], w[N]; //每件物品的体积 价值
int f[N][N]; //f[i][j]不超过第i件物品 背包容量不超过j /*
4 5
1 2
2 4
3 4
4 5
*/int main() {cin n m;for (int i 1; i n; i) {cin v[i] w[i]; //输入体积 价值 }//f[0][0~m]默认为零无需进行初始化for (int i 1; i n; i) {for (int j 1; j m; j) {if (j v[i]) f[i][j] max(f[i-1][j], w[i] f[i-1][j-v[i]]);else f[i][j] f[i-1][j];}} cout f[n][m] endl;
}滚动数组优化版本 -- 一维DP(01背包问题终极写法) dp[i][j]--dp[j]删掉了i这个集合相当于现在每次只存放了前一个物品的[背包不超过j]的最大值。 比如第一次dp[]存放的是不超过第一个物品的[背包不超过j] 的最大值。第二次在第一次的基础上进行更新这里需要注意背包集合的遍历顺序需要思考如果还是正序遍历会带来什么影响没错因为每次都要利用到之前的[背包不超过j]的集合如果正序遍历那么就会从小的背包开始更新那么就会把上一次的背包最大值覆盖掉遍历到后面j大起来了要使用上一次也就是[物品不超过i-1]的[背包不超过j]的集合来进行更新就会碰到滚动数组数据被覆盖了的问题。所以需要注意的就是要从大的背包开始遍历j这样就可以避免dp[背包容量j]被覆盖掉进行滚动的更新。 #include iostream
// 01背包1维写法 const int N 10010;
int n, m; //物品个数 背包容量
int v[N], w[N]; //每个物品的体积 价值
int dp[N]; //优化前不超过i的物品的体积和不超过j的背包 -- 优化后 不超过i件物品 --最大价值
/*输入数据不变
4 5
1 2
2 4
3 4
4 5
*/
using namespace std;int main() {cin n m;for (int i 0; i n; i) {cin v[i] w[i];}for (int i 1; i n; i) {for (int j m; j v[i]; j-- ) {dp[j] max(dp[j], dp[j-v[i]] w[i]);}}cout dp[m] endl;
}
