完全背包
2026-01-03 12:01:58
发布于：四川
4阅读
0回复
0点赞
二维优化版
四要素分析
状态：dp[i][j] 表示前 i 种物品、容量 j 的最大价值（与暴力版一致）。
转移：
若 j < w[i]（容量不足，无法选第 i 种物品），则 dp[i][j] = dp[i-1][j]（继承前 i-1 种物品的状态）；
若 j ≥ w[i]（容量足够，可重复选第 i 种物品），则 dp[i][j] = max(dp[i-1][j], dp[i][j - w[i]] + v[i])（dp[i][j - w[i]] 已包含第 i 种物品的多次选择，无需枚举 k）。
边界：dp[0][j] = 0、dp[i][0] = 0（与暴力版一致）。
答案：dp[n][m]（与暴力版一致）。
void complete_packsack_small_optimize(){//完全背包：二维优化（省略次数枚举）
for(int i=1;i<=n;i++){//遍历物品种类
for(int j=0;j<=m;j++){//遍历背包容量
if(j<w[i]) dp[i][j]=dp[i-1][j];//容量不足，继承前一状态（转移1）
else dp[i][j]=max(dp[i-1][j],dp[i][j-w[i]]+v[i]);//容量足够，复用当前物品状态（转移2）
}
}
}
一维优化版（正向迭代）：
四要素分析：
状态：dp2[j] 表示容量 j 的最大价值（压缩为一维，通过迭代顺序保证“物品可重复选”）。
转移：对每种物品 i，正向遍历容量 j = w[i] ~ m，则 dp2[j] = max(dp2[j], dp2[j - w[i]] + v[i])（正向迭代允许 dp2[j - w[i]] 已包含当前物品的选择记录，实现重复选）。
边界：dp2[j] = 0（初始所有容量的价值为0，无物品时价值为0）。
答案：dp2[m]（容量 m 的最大价值）。
void complete_packsack_optimize(){//完全背包：一维正向迭代（核心优化版）
cin>>n>>m;
memset(dp2,0,sizeof dp2); // 边界初始化（所有容量初始价值为0）
for(int i=1;i<=n;i++){//遍历物品种类
// 正向迭代：允许同一物品被多次选择（转移关键）
for(int j=w[i];j<=m;j++){
dp2[j]=max(dp2[j],dp2[j-w[i]]+v[i]); // 状态转移
}
}
cout<<dp2[m]<<endl; // 答案（容量m的最大价值）
}
这里空空如也
有帮助，赞一个