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

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

01背包问题 二维

文章链接

思路：dp[i][j] 表示从下标为[0-i]的物品里任意取，放进容量为j的背包，价值总和最大是多少。 不放物品i：由dp[i - 1][j]推出，即背包容量为j，里面不放物品i的最大价值，此时dp[i][j]就是dp[i - 1][j]。(其实就是当物品i的重量大于背包j的重量时，物品i无法放进背包中，所以背包内的价值依然和前面相同。) 放物品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得到的最大价值 所以递归公式： dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - weight[i]] + value[i]);

代码

void test_2_wei_bag_problem1() { vector<int> weight = {1, 3, 4}; vector<int> value = {15, 20, 30}; int bagweight = 4; // 二维数组 vector<vector<int>> dp(weight.size(), vector<int>(bagweight + 1, 0)); // 初始化 for (int j = weight[0]; j <= bagweight; j++) { dp[0][j] = value[0]; } // 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]); } } cout << dp[weight.size() - 1][bagweight] << endl; } int main() { test_2_wei_bag_problem1(); } 01背包问题 一维

文章链接

思路：用一维来解决背包问题要注意，体积应该从大到小递减，如果从小到大递增遍历，会重复加入物品。应该先遍历物品，然后遍历体积，不能颠倒。颠倒会导致物品只会添加一次。

代码

void test_1_wei_bag_problem() { vector<int> weight = {1, 3, 4}; vector<int> value = {15, 20, 30}; int bagWeight = 4; // 初始化 vector<int> dp(bagWeight + 1, 0); for(int i = 0; i < weight.size(); i++) { // 遍历物品 for(int j = bagWeight; j >= weight[i]; j--) { // 遍历背包容量 dp[j] = max(dp[j], dp[j - weight[i]] + value[i]); } } cout << dp[bagWeight] << endl; } int main() { test_1_wei_bag_problem(); } 416. 分割等和子集

题目链接：416. 分割等和子集 文章链接 状态：没思路，不知道怎么转化为背包问题。

思路：体积从sum / 2开始递减。

代码

class Solution { public: bool canPartition(vector<int>& nums) { int sum = 0; vector<int> dp(10001,0); for (int i = 0; i < nums.size(); i++) sum += nums[i]; int target = sum / 2; if (sum % 2 == 1) return false; for (int i = 0; i < nums.size();i++) for (int j = target; j >= nums[i]; j--) { dp[j] = max(dp[j], dp[j - nums[i]] + nums[i]); } if (dp[target] == target) return true; else return false; } };