有点抽象
0-1背包
卡码网：携带研究材料（第六期模拟笔试）
动态规划
思路
二维：
- 意义：0~i物品内，放进容量为j的背包，最大价值为dp[i][j]
- 递推：
dp[i][j] = max(dp[i-1][j-weight[i],dp[i-1][j]) - 初始化：第一列为0，第一行
j>=weight[0]时赋值为value[0] - 遍历：先背包再物品/先物品再背包 均可
（每层元素都由上一层推出。正上、左上区）
一维：
- 意义：容量为j的背包最大价值为dp[j]
- 递推：
dp[j] = max(dp[j],dp[j-weight[i]] + value[i])取、不取 - 初始化：初始化为0
- 遍历：先物品再背包，倒序
（每层元素由当前层推出。自身、左区。每层元素既是本层，也是上层。每轮背包遍历，更新前的值表示上层，更新后的值为当前层）
复杂度分析
时间复杂度：O(N^2)。
空间复杂度：二维数组O(N^2)，一维数组O(N)。
代码实现
二维数组版：
#include<iostream>
#include<vector>
#include <algorithm>
using namespace std;
/*
意义：0~i物品内，放进容量为j的背包，最大价值为dp[i][j]
递推：dp[i][j] = max(dp[i-1][j-weight[i],dp[i-1][])
初始化：第一列为0，第一行j>=weight[0]时赋值为value[0]
遍历：先背包再物品/先物品再背包 均可
*/
int main(){
int M = 0; // item types
int N = 0; // capacity
cin>>M;
cin>>N;
vector<int> weight(M,0);
vector<int> value(M,0);
for(int i = 0;i < M;i++){
cin>>weight[i];
}
for(int i = 0;i < M;i++){
cin>>value[i];
}
vector<vector<int>> dp(M,vector<int>(N+1,0));
for(int j = 1;j <= N;j++){
if(j >= weight[0]) dp[0][j] = value[0];
}
for(int i = 1;i < M;i++){
for(int j = 1;j <= N;j++){
if(j >= weight[i]){ // 如果
dp[i][j] = max( dp[i-1][j],dp[i-1][j-weight[i]] + value[i] );
}else{
dp[i][j] = dp[i-1][j];
}
}
}
cout<<dp[M-1][N]<<endl;
return 0;
}
一维数组版：
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
/*
意义：容量为j的背包最大价值为dp[j]
递推：dp[j] = max(dp[j],dp[j-weight[i]] + value[i]) 取、不取
初始化：初始化为0
遍历：先物品再背包，倒序
*/
int main(){
int M = 0; // count of types
int N = 0; // capacity
cin>>M;
cin>>N;
vector<int> weight(M,0);
vector<int> value(M,0);
for(int i = 0;i < M;i++){
cin>>weight[i];
}
for(int i = 0;i < M;i++){
cin>>value[i];
}
vector<int> dp(N+1,0);
for(int i = 0;i < M;i++){ // 先遍历物品
for(int j = N;j >= weight[i];j--){ // 再遍历背包（倒序）
dp[j] = max(dp[j],dp[j-weight[i]] + value[i]);
}
}
cout<<dp[N];
return 0;
}
分割等和子集
leetcode：416. 分割等和子集
动态规划
思路
容量和价值都是nums[i]
- 意义：容量为j的背包最大价值为
dp[j]if(dp[sum/2] == sum/2) return true; - 容量
sum/2的背包装的最大价值为sum/2 - 初始化：为0
- 遍历：先物品再背包，倒序
复杂度分析
时间复杂度：O(N^2)。
空间复杂度：O(N)。
代码实现
C++：
class Solution {
public:
/*
可看成0-1背包问题，weight和value都是数字大小
意义：容量为j的背包最大价值为dp[j] if(dp[sum/2] == sum/2) return true;
容量sum/2的背包装的最大价值为sum/2
初始化：为0
遍历：先物品再背包，倒序
*/
bool canPartition(vector<int>& nums) {
int sum = 0;
for(int num : nums) sum += num;
if(sum%2 == 1) return false; // 总和为奇数，不可能对半分
int n = nums.size();
vector<int> dp(sum/2 + 1,0);
for(int i = 0;i < n;i++){
for(int j = sum/2;j >= nums[i];j--){
dp[j] = max(dp[j],dp[j - nums[i]] + nums[i]);
}
}
if(dp[sum/2] == sum/2) return true;
else return false;
}
};
TS：
/**
意义：容量为j的背包，装的最大价值是dp[j] (weight[]和value[]都是nums[])
递推：dp[j] = max(dp[j],dp[j - nums[i]] + nums[i])
初始化：置为0
遍历：先物品再背包，倒序
*/
function canPartition(nums: number[]): boolean {
let sum = 0;
nums.forEach((item) => sum += item);
if(sum%2 == 1) return false;
let dp = new Array(sum/2 + 1).fill(0);
for(let i = 0;i < nums.length;i++){
for(let j = sum/2;j >= nums[i];j--){
dp[j] = Math.max(dp[j],dp[j - nums[i]] + nums[i]);
}
}
if(dp[sum/2] === sum/2) return true;
else return false;
};