代码随想录算法训练营第三十三天| 01背包问题 二维 01背包问题 一维 416. 分割等和子集

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 }