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

卡码网 01背包问题 二维

题目链接：01背包问题 二维

踩坑：在考虑当前物品时，应先考虑当前的背包能不能放得下当前物品

思路：

1. 动态数组的含义：dp[i][j]：物品[0, i]在容量为 j 的背包中的最大价值
2. 递推公式：对于dp[i][j]，如果不放入当前物品 i，其价值为dp[i-1][j]，如果放入当前物品 i，其价值为dp[i-1][ j - weight[ i ] ]+price[i]。这里重点考虑的就是如何体现出放与不放
3. 初始化动态数组：有递推公式可知，当前状态依赖其二维数组中上方与左上方的状态，因此应初始化第一行，第一列。
4. 遍历顺序：因为当前状态依赖于上方与左上方，所以可以先遍历物品，再遍历背包，也可以先遍历背包，再遍历物品。

代码：

# include<iostream>
# include<vector>
using namespace std;
int main()
{
    int n;
    int c;
    cin>>n>>c;
    vector<int> w(n, 0);
    for(int i = 0; i < n; i++)
    {
        int t;
        cin>>t;
        w[i] = t;
    }
    vector<int> p(n, 0);
    for(int i = 0; i < n; i++)
    {
        int t;
        cin>>t;
        p[i] = t;
    }
    vector<vector<int>> dp(n, vector<int>(c+1, 0));
    
    for(int i = 0; i <= c; i++)
    {
        if(i >= w[0]) dp[0][i] = p[0];
    }
    
    for(int i = 1; i < n; i++)
    {
        for(int j = 1; j <= c; j++)
        {
            if(j < w[i]) dp[i][j] = dp[i-1][j];
            else dp[i][j] = max(dp[i-1][j], dp[i-1][j-w[i]]+p[i]);
            
        }
    }
    cout<<dp[n-1][c];
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41

卡码网 01背包问题 一维

题目链接：01背包问题 一维

踩坑：看了视频

思路：一维01背包问题是二维01背包问题的优化版，其核心在于，因为01背包当前行只依赖于上一行，所以可以只维护一个一维数组滚动更新。

1. dp数组的含义：dp[j]：背包为 j 时能装的最大价值
2. 递推公式：同样考虑放与不放，不放当前物品时dp[j]的最大价值还是dp[j]，放当前物品时dp[j] = dp[j-w[i]]+p[i]。
3. 初始化：一维与二维不同，一维依赖的是本身和左边的数且第一行根据递推公式并不需要特殊处理，所以初始化成0以保证不会影响max即可。
4. 遍历顺序：由递推公式可知，当前状态依赖于本身与左边且新状态会覆盖旧状态，因此如果从左向右遍历会新旧状态冲突，只能从右向左即倒序遍历。

代码：

# include<iostream>
# include<vector>
using namespace std;
int main()
{
    int n;
    int c;
    cin>>n>>c;
    vector<int> w(n, 0);
    for(int i = 0; i < n; i++)
    {
        int t;
        cin>>t;
        w[i] = t;
    }
    vector<int> p(n, 0);
    for(int i = 0; i < n; i++)
    {
        int t;
        cin>>t;
        p[i] = t;
    }
    vector<int> dp(c+1,0);
    
    for(int i = 0; i < n; i++)
    {
        for(int j = c; j >= w[i]; j--)
        {
            dp[j] = max(dp[j], dp[j-w[i]]+p[i]);
        }
    }
    cout<<dp[c];
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34

LeetCode 416.分割等和子集

题目链接：416. 分割等和子集

踩坑：倒序–

思路：有以下几个槛

1. 子集总和的一半就是要求的子集的和
2. 元素的大小等于元素的价值
3. 子集的和就是背包的容量
4. 背包的最大价值等于容量说明有解
   想到以上的点就可以抽象为01背包问题了

代码：

class Solution {
public:
    bool canPartition(vector<int>& nums) {
        int n = nums.size();
        int c;
        if(accumulate(nums.begin(), nums.end(), 0)%2) return false;
        else c = accumulate(nums.begin(), nums.end(), 0)/2;
        vector<int> dp(c+1, 0);
        for(int i = 0; i < n; i++)
        {
            for(int j = c; j >= nums[i]; j--)
            {
                dp[j] = max(dp[j], dp[j-nums[i]] + nums[i]);
            }
        }
        if(dp[c] == c) return true;
        else return false;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19