[数据结构与算法]【算法/动态规划/01背包】题解+详细备注（共4题）

01背包模板

使用二维数组

• 确定dp数组以及下标的含义：dp[i][j] 表示从下标为[0-i]的物品里任意取，放进容量为j的背包，价值总和最大是多少。
• 确定递推公式：

1. 不放物品i：由dp[i - 1][j]推出，即背包容量为j，里面不放物品i的最大价值，此时dp[i][j]就是dp[i - 1][j]。(其实就是当物品i的重量大于背包j的重量时，物品i无法放进背包中，所以被背包内的价值依然和前面相同。)
2. 放物品i：由dp[i - 1][j - weight[i]]推出，dp[i - 1][j - weight[i]] 为背包容量为j - weight[i]的时候不放物品i的最大价值，那么dp[i - 1][j - weight[i]] + value[i] （物品i的价值），就是背包放物品i得到的最大价值
3. 所以递归公式：

dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - weight[i]] + value[i]);

• dp数组的初始化

// 初始化 dp
vector<vector<int>> dp(weight.size(), vector<int>(bagweight + 1, 0));
for (int j = weight[0]; j <= bagweight; j++) {
    dp[0][j] = value[0];
}

• 确定遍历顺序

1. 先遍历物品，再遍历背包

// weight数组的大小 就是物品个数
for(int i = 1; i < weight.size(); i++) { // 遍历物品
    for(int j = 0; j <= bagweight; j++) { // 遍历背包容量
        if (j < weight[i]) dp[i][j] = dp[i - 1][j]; 
        else dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - weight[i]] + value[i]);

    }
}

2. 先遍历背包，再遍历物品

// weight数组的大小 就是物品个数
for(int j = 0; j <= bagweight; j++) { // 遍历背包容量
    for(int i = 1; i < weight.size(); i++) { // 遍历物品
        if (j < weight[i]) dp[i][j] = dp[i - 1][j];
        else dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - weight[i]] + value[i]);
    }
}

使用一维数组

• 确定dp数组以及下标的含义：dp[j]表示容量为j的背包，所背的物品价值可以最大为dp[j]
• 确定递推公式：

dp[j] = max(dp[j], dp[j - weight[i]] + value[i]);

• dp数组的初始化：dp[0] = 0
• 确定遍历顺序

for(int i = 0; i < weight.size(); i++) { // 遍历物品
    for(int j = bagWeight; j >= weight[i]; j--) { // 遍历背包容量（从大到小，倒序遍历是为了保证物品i只被放入一次！）
        dp[j] = max(dp[j], dp[j - weight[i]] + value[i]);

    }
}

416.分割等和子集

class Solution {
public:
	// 01背包求解（一个商品只能放入一次，多重背包可以放入多次）
    bool canPartition(vector<int>& nums) {
        int nSum = accumulate(nums.begin(),nums.end(),0);
        if(nSum%2 == 1) return false;
        int target = nSum/2;
        // 1.确定dp数组以及下标的含义
        // 01背包中：dp[j]表示容量为j的背包，所背的物品价值可以最大为dp[j]
        // 套到本题，dp[j]表示 背包总容量是j，最大可以凑成j的子集总和为dp[j]
        vector<int> dp(target+1);// 注意是：target+1，表示背包容量
        // 3.dp数组初始化：全部初始化为0
		
		// 4.遍历顺序 
		// 01背包的遍历顺序是先遍历物品，再由大到小遍历背包容量
		// 套到本题，先外层从小到大遍历物品nums；内层从大到小遍历容量target
        for(int i{};i<nums.size();++i){
            for(int j = target;j>=nums[i];--j){
            	// 2.确定递推公式
            	// 01背包的递推公式：dp[j] = max(dp[j],dp[j-weight[i]] + value[i]);
            	// 套到本题：dp[j] = max(dp[j],dp[j-nums[i]] + nums[i]);
                dp[j] = max(dp[j-nums[i]] + nums[i],dp[j]);
            }
        }

        return dp[target] == target;
    }
};

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

class Solution {
public:
	// 01背包解决问题
    int lastStoneWeightII(vector<int>& stones) {
    	// 1.确定dp数组以及下标的含义
    	// 01背包：dp[j]表示容量为j的背包，所背的物品价值可以最大为dp[j]
    	// 本题：dp[j]表示容量为j的背包，最多可以背dp[j]这么重的石头
        vector<int> dp(15001);
        // 3.dp数组的初始化：都初始化为0
        int targetSum = accumulate(stones.begin(),stones.end(),0);
        int target = targetSum/2;
        // 4.确定遍历顺序
        // 01背包：外层从小到大遍历物品，内层从大到小遍历背包容量
        for(int i{};i<stones.size();++i){
            for(int j = target;j>=stones[i];j--){
            	// 2.确定递推公式
            	// 01背包：dp[j] = max(dp[j],dp[j-weight[i]]+value[i]);
            	// 本题：dp[j] = max(dp[j],dp[j-stones[i]] + stones[i])
                dp[j]=max(dp[j],dp[j-stones[i]] + stones[i]);
            }
        }

        return targetSum - dp[target] - dp[target];
    }
};

494.目标和

class Solution {
public:
	// 01背包解决问题
	// 重点要想到： left - (sum - left) = target -> left = (target + sum)/2 
	// 所以求组合类问题的公式，都是类似这种： dp[j] += dp[j - nums[i]]
    int findTargetSumWays(vector<int>& nums, int target) {
        int tSum = accumulate(nums.begin(),nums.end(),0);
        if(abs(target) > tSum) return 0; ?/

        tSum+=target;
        if(tSum%2) return 0;

        int target1 = tSum/2;
        // 1.确定dp数组以及下标的含义
        // 01背包：dp[j]表示容量为j的背包，所背的物品价值最大可以为dp[j]
        // 本题：dp[j]表示填满j这么大的背包，一共有dp[j]种方法
        vector<int> dp(target1+1);
        // 3.dp数组初始化
        dp[0] = 1;

		// 4.确定遍历顺序
		// 01背包：外层从小到达遍历物品，内层从大到小遍历背包容量
		// 本题：外层从小到达遍历物品，内层从大到小遍历背包容量
        for(int i{};i<nums.size();++i){
            for(int j = target1;j>=nums[i];--j){
            	// 2.确定递推公式
            	// 01背包：dp[j] = max(dp[j],dp[j-weight[i]]+value[i])
            	// 本题：dp[j] += dp[j-nums[i]]
                dp[j] += dp[j-nums[i]];
            }
        }

        return dp[target1];
    }
};

474.一和零

class Solution {
public:
    int findMaxForm(vector<string>& strs, int m, int n) {
    	// 1.确定dp数组以及下标的含义
    	// 01背包：dp[j] = max(dp[j],dp[j-weight[i]] + value[i])
    	// 本题：dp[i][j]表示最多有i个0和j个1的str的最大子集为dp[i][j]
        vector<vector<int>> dp(m+1,vector<int>(n+1));
		
		// 3.dp数组初始化
		
		// 4.确定遍历顺序
		// 01背包：外层从小到大遍历物品，内层从大到小遍历背包容量
        for(int i{};i<strs.size();++i){
            int oneNum{},zeroNum{};
            for(char &c : strs[i]){
                if(c == '0') zeroNum++;
                else if(c == '1') oneNum++;
            }

            for(int j = m;j>=zeroNum;--j){
                for(int k = n;k>=oneNum;--k){
                	// 2.确定递推公式
                	// 01背包：dp[j] = max(dp[j],dp[j-weight[i]] + values[i])
                	// 本题：dp[i][j] = max(dp[i][j], dp[i - zeroNum][j - oneNum] + 1);
                    dp[j][k] = max(dp[j][k],dp[j-zeroNum][k-oneNum] + 1);
                }
            }
        }

        return dp[m][n];
    }
};

创作打卡挑战赛

赢取流量/现金/CSDN周边激励大奖