代码随想录算法训练营33期 第四十三天|416.分割等和子集、1049.最后一块石头的重量II、474.一和零

416.分割等和子集

// 1:dp[i]容量为i的背包的价值
// 2:dp[0]=0 dp[1]=dp[0]+value[1]
// 3:dp[i]=max(dp[i], dp[i-weight[i]]+value[i])
// 4:遍历顺序：物品按序号递增遍历，容量按大小降序遍历
// 5:打印dp
class Solution {
public:
    bool canPartition(vector<int>& nums) {
        int sum = 0;
        for (int i=0; i<nums.size(); i++){
            sum+=nums[i];
        }
        if (sum%2==1) return false;
        int target = sum/2;
        vector<int> dp(10001, 0); //最大容量

        //下面两个循环的含义是，遍历每个物品，
        for (int i=1; i<nums.size(); i++){ //i是物品
            for (int j=target; j>=nums[i]; j--){ //j是容量
                dp[j]=max(dp[j], dp[j-nums[i]]+nums[i]); //max(dp[j], dp[j-nums[i]]+nums[i])中max里的dp[j]指的是遍历上一个物品时得到的当前容量下的最大价值
                                                        // dp[j]实际是由dp[i-1][j]得来。
            }
        }
        cout << target << endl;
        
        for(int value : dp){
            cout << value <<" ";
        }
        cout << endl;
        
        if (dp[target]==target) return true;
        else return false;
    }
};

思路就是排除所有元素的和无法整除的情况后，如果数组内元素可以拼凑出和的一半就为true。

1049.最后一块石头的重量II

// 思路：将石头分为重量相似的两堆
// 1、dp[j] 重量j的背包的最大价值
// 2、dp[0] = stones[0];
// 3、递推公式dp[j]=min(dp[j], dp[j-1]-stone[i]);
// 4、顺序：按序号升序遍历物品种类i，按背包容量降序尝试插入种类i
// 5、打印dp
class Solution {
public:
    int lastStoneWeightII(vector<int>& stones) {
        int sum=0;
        for (int i : stones){
            sum+=i;
        }
        int target=sum/2;
        cout << "traget = " << target << endl;
        vector<int> dp(10001, 0);
        dp[0] = 0;
        for (int i=0; i<stones.size(); i++){
            for (int j=target; j>=stones[i]; j--){
                dp[j] = max(dp[j], dp[j-stones[i]]+stones[i]);
            }
        }
        for (int i=0; i<dp.size(); i++){
            cout << dp[i] << " ";
        }
        cout << endl;

        return sum-2*dp[target];
    }
};

474.一和零

//dp[i][j]的含义，容量为i个0，j个1时，可存储元素的个数

class Solution {
public:
    int findMaxForm(vector<string>& strs, int m, int n) {
        vector<vector<int>> dp(m+1, vector<int>(n+1, 0));
        dp[0][0]=0;
        int x=0, y=0;
        for (string item : strs){ //遍历物品即可用字符串
            x=0;
            y=0;
            for (char c : item){
                if (c=='0') x++;
                else y++;
            }
            for (int i=m; i>=x; i--){
                for (int j=n; j>=y; j--){
                    dp[i][j] = max(dp[i][j], dp[i-x][j-y] + 1);     //如果当前字符串满足要求，则就在不含这个字符串的基础上+1
                }
            }
        }
        return dp[m][n];
    }
};