01背包问题 二维
思路
本题没有特定的题目。有n件物品和一个最多能背重量为w 的背包。第i件物品的重量是weight[i]，得到的价值是value[i] 。每件物品只能用一次，求解将哪些物品装入背包里物品价值总和最大。
实现
- dp数组及其含义
dp[i][j]表示背包的最大重量是j，可以从0-i中物品中任取物品。此时背包所装物品的最大价值为dp[i][j] - 递推公式
- 不放物品
当不放入新物品时，总的最大价值没有变，仍然为dp[i-1][j] - 放物品
当放入新物品时，需要先取出物品，再放入物品，因此价值为dp[i-1][j-weight[i]] + value[i] - 递推公式
dp[i][j] = max(dp[i-1][j], dp[i-1][j-weight[i]] + value[i])
-
初始化
当背包的重量为0时，背包中所装物品的价值一定为0；
当背包中只有物品0时，如果背包的重量大于weight[0],那么背包的总价值为value[0]
-
遍历顺序
遍历过程所需要的时该位置左上角的元素，因此先便利物品还是先遍历背包都能得出正确结果。
点击查看代码
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();
}
复杂度分析
- 时间复杂度：O(n * m)，m为物品种类，n为背包重量
- 空间复杂度：O(n * m)
01背包问题 一维
思路
- 数组及其下标含义
dp[j]表示背包重量为j时，背包中物品的最大价值 - 递推公式
dp[j] = max(dp[j], dp[j - weight[i]] + value[i]) - 初始化
当背包质量为0时，其中的价值一定为0；
因此初始化时，初始化所有质量为0即可。 - 遍历顺序
先重量再物品那么背包中只能装有一个物品，(会不断刷新背包中的物品)只能先物品再背包。
因为递推中需要左上角的元素，因此，遍历背包需要倒序遍历。
实现
点击查看代码
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();
}
复杂度分析
- 时间复杂度：O(m*n)，m为物品种类，n为背包重量
- 空间复杂度：O(n)
416. 分割等和子集
思路
dp[i]表示和为i时的最大子集。如果dp[i] == sum/2,说明可以分割
实现
点击查看代码
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;
vector<int> dp(10001,0);
for(int i = 0; i < nums.size(); i++) {
for(int j = sum/2; j >= nums[i]; j--) {
dp[j] = max(dp[j], dp[j-nums[i]] + nums[i]);
}
cout<<dp[sum/2]<<endl;
}
if(dp[sum/2] == sum/2) return true;
else return false;
}
};
复杂度分析
- 时间复杂度：O(n^2)
- 空间复杂度：O(n)