aksz 背包
2024-06-30 17:05:47
发布于:广东
#背包
0/1背包
容量为V的背包
需要在k个物品中选取并装入
只有装/不装两种状态
v[i]
w[i]
dp[i][j]
求解dp[i][j]
必然已求得dp[1i-1][1j-1]
不装入:dp[i][j] = dp[i-1][j]
选择装入dp[i][j] = dp[i-1][j-v[i]]+w[i];
初始化:dp[0][0~v] = 0;
答案:dp[k][v]
滚动数组优化
int now = 0,last = 1;
void solve(){
for(int i = 1;i<=n;i++){
now^=1;
last^=1;
for(int j = 1;j<=V;j++){
if(j>=v[i]){
dp[now][j] = max(dp[last][j],dp[last][j-v[i]]+w[i]);
}else {
dp[now][j] = dp[last][j];
}
}
}
}
压成一维
void solve(){
for(int i = 1;i<=m;i++){
for(int j = V;j>=v[i];j--){
dp[j] = max(dp[j],dp[j-v[i]]+w[i]);
}
}
}
#无限背包
容量为V的背包
需要在k个物品中选取并装入
每种物品可以选取任意个数
每个物品占用空间v[i],价值w[i];
不装入
dp[i][j] = dp[i-1][j]
装入
dp[i][j] = dp[i][j-v[i]]+w[i];
j的循环从小到大
一个int4个字节
32位一个int
这里空空如也
有帮助,赞一个