01背包问题 二维
要求：
有一个背包，他只能装4KG，分别有三个物品： 1 15；3 20； 4 30 ——》需要物品价值最大
dp[i][j] 含义：
在放物品I 的时候在J背包容量下的物品最大值
递推公式：
1,不放当前物品：dp[i-1][j]
2，放当前物品：(dp[i-1][j]) ->不应该是在当前容量下，i-1的最大价值，应该是：dp[i-1][j-weight[i]] 如果i 要3KG，那么就是i-1在1KG 下的最大值
初始化:
1，容量为0时，全为0，
2，物品0 对于J来说如果容量大于，那么就是value[0]，否则为0
测试代码：
// vector<int> weight = {1, 3, 4};
// vector<int> value = { 15, 20, 30 };
// int bagweight = 4;
代码：
1 // 01背包问题 2 // 要求：有一个背包，他只能装4KG，分别有三个物品： 1 15；3 20； 4 30 ——》需要物品价值最大 3 // dp[i][j] 含义：在放物品I 的时候在J背包容量下的物品最大值 4 // 5 // 递推公式： ——》疑问，如果放当前物品，但是其实不放，放下一个才是最大值，这是怎么实现的，也就是如何实现多个解，然后选择最大值？ 6 // 1,不放当前物品：dp[i-1][j] 7 // 2，放当前物品：(dp[i-1][j]) ->不应该是在当前容量下，i-1的最大价值，应该是：dp[i-1][j-weight[i]] 如果i 要3KG，那么就是i-1在1KG 下的最大值 8 // 9 // 初始化: 10 // 1，容量为0时，全为0， 11 // 2，物品0 对于J来说如果容量大于，那么就是value[0]，否则为0 12 // 13 // 测试代码： 14 // vector<int> weight = {1, 3, 4}; 15 // vector<int> value = { 15, 20, 30 }; 16 // int bagweight = 4; 17 // 18 int test_2_wei_bag_problem1(vector<int>& weight, vector<int> &value, int& bagweight) 19 { 20 vector<vector<int>> dp(weight.size(), vector<int>(bagweight+1, 0)); 21 22 for (int i = 0; i <= bagweight; i++) 23 { 24 if (weight[0] <= i) 25 { 26 dp[0][i] = value[0]; 27 } 28 } 29 30 for (int i = 1; i < dp.size(); i++) 31 { 32 for (int j = 0; i <= bagweight; j++) 33 { 34 if (bagweight < weight[i]) 35 { 36 dp[i][j] = dp[i - 1][j]; 37 continue; 38 } 39 40 int cur1 = dp[i - 1][j]; 41 int cur2 = value[i] + dp[i - 1][j - weight[i]]; 42 43 dp[i][j] = max(cur1, cur2); 44 } 45 } 46 47 int result = INT_MIN; 48 for (int i = 0; i < dp.size(); i++) 49 { 50 if (result < dp[i][bagweight]) 51 { 52 result = dp[i][bagweight]; 53 } 54 } 55 56 return result; 57 }
01背包问题 一维
dp[J]：
当容量为 J 的时候的最大值
递推公式：
// J : 当前容量 I：当前物品
// 1，不放当前物品：dp[J] = dp[J]
// 2，放当前物品： dp[J] = dp[J - weight[I]] + value[I]
初始化：
// 1，dp[o] = 0
遍历顺序：
// 设想当容量为1的时候放了一个A，容量为2的时候再放了物品A dp[1] = 20 dp[2] = dp[1]+20 = 40
// 如果dp[i][j]
// dp[A][1] ； dp[B][2] = dp[A][1]+B 而不是加A
// 理想的情况：dp[1] 放了物品A，那么dp[2] 的时候就不要再放物品A了
// 因为每次是针对单个容量来搞的，并不代表和dp[0]有任何联动？——》不正确
// 先看物品A， 然后让容量从高到底来做，——》这样和dp[i-1] 有关系么？ ——》 有关系，可以看下面
// 可以保证A在每个容量里只放了依次
// 当下一个容量的时候，就可以用上一个物品了
代码
1 // 使用一个一维数组 来搞动态规划 2 // dp[J]：当容量为 J 的时候的最大值 3 // 递推公式： 4 // J : 当前容量 I：当前物品 5 // 1，不放当前物品：dp[J] = dp[J] 6 // 2，放当前物品： dp[J] = dp[J - weight[I]] + value[I] 7 // 8 // 初始化： 9 // 1，dp[o] = 0 10 // 遍历顺序： 11 // 设想当容量为1的时候放了一个A，容量为2的时候再放了物品A dp[1] = 20 dp[2] = dp[1]+20 = 40 12 // 如果dp[i][j] 13 // dp[A][1] ； dp[B][2] = dp[A][1]+B 而不是加A 14 // 15 // 理想的情况：dp[1] 放了物品A，那么dp[2] 的时候就不要再放物品A了 16 // 因为每次是针对单个容量来搞的，并不代表和dp[0]有任何联动？——》不正确 17 // 先看物品A， 然后让容量从高到底来做，——》这样和dp[i-1] 有关系么？ ——》 有关系，可以看下面 18 // 可以保证A在每个容量里只放了依次 19 // 当下一个容量的时候，就可以用上一个物品了 20 // 21 int test_1_wei_bag_problem(vector<int>& weight, vector<int>& value, int& bagweight) 22 { 23 vector<int> dp(bagweight + 1, 0); 24 25 for (int i = 0; i < weight.size(); i++) 26 { 27 for (int j = bagweight; j >= 0; j--) 28 { 29 if (j < weight[i]) 30 { 31 continue; 32 } 33 else 34 { 35 dp[j] = max(dp[j], dp[j - weight[i]] + value[i]); 36 } 37 } 38 } 39 40 return dp[bagweight]; 41 }