代码随想录第九章动态规划part03 01背包问题一维 416. 分割等和子集

01背包问题一维

#include <bits/stdc++.h>
using namespace std;
int main(){int n, bagWeight;cin >> n >> bagWeight;std::vector<int> value(n, 0);std::vector<int> weight(n, 0);for (int i = 0; i < n; i++) cin >> weight[i];for (int i = 0; i < n; i++) cin >> value[i];std::vector<int> result(bagWeight + 1, 0);for (int i = weight[0]; i<=bagWeight; i++) result[i] = value[0];for (int i = 1; i < n; i++){for (int j = bagWeight; j >= 0; j--){if (j >= weight[i]) result[j] = max(result[j], result[j - weight[i]] + value[i]);}}cout << result[bagWeight];return 0;
}

一维与二维的区别在于记录最优价值的数组是一维还是二维，从随想录所给的计算思路可以看出，在计算二维数组的过程中，只需要知道上一行的数据即可计算下一行的最优价值，所以完全可以只借助一个一维数组，不断迭代数组的值，求取最终的最优价值。

416. 分割等和子集

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 != 0) return false;vector<int> value((sum / 2) + 1, 0);for (int i = nums[0]; i < value.size(); i++) value[i] = nums[0];for (int i = 1; i < nums.size(); i++){for (int j = sum / 2; j>=0; j--){if (j >= nums[i]) value[j] = max(value[j], value[j - nums[i]] + nums[i]);}}if (value[sum / 2] != sum / 2) return false;return true;}
};

这题乍一看首先想到的思路就是回溯，不过现在是动态规划了。如果将数字集合看做重量与价值相等的物品集合，如果集合能分为两个和相等的子集，在背包问题中也就意味着在背包最大容量为所有物品重量和的1/2时，最多能装下重量为所有物品和的1/2的物品，因为物品价值与重量相等，所以最优价值不会大于背包容量，但如果最终最优价值低于背包容量，也就代表数字集合无法被分为两个和相等的部分。

代码随想录第九章动态规划part03