你的代码错在数组初始化和边界条件上。e数组没初始化,全是垃圾值,导致max计算出错。改成这样:
先加 memset(e,0,sizeof(e));
for循环从i=0到m,j=0到n初始化e[0][j]=0,e[i][0]=0;
物品循环i=1到m,容量j=a[i]到n(反向),e[j]=max(e[j],e[j-a[i]]+b[i]);
用一维数组优化,空间省。
主要错误分析
看了你的代码,主要问题有几个:1. e数组没有初始化,里面是随机垃圾值,所以e[i-1][j]什么的都是错的。2. 当j-a[i]>=0时,e[i][j-a[i]]可能是垃圾值。3. i从1开始,但e[0][j]没定义。4. 输出i=0到m,但e[0][j]没设。必须先把e全清0。
完整修正代码
#include <bits/stdc++.h>
using namespace std;
int n,m,a[101],b[101];
int e[101][101];
int main(){
cin>>n>>m;
memset(e,0,sizeof(e));
for(int i=1;i<=m;i++){
cin>>a[i]>>b[i];
}
for(int i=1;i<=m;i++){
for(int j=0;j<=n;j++) e[i][0]=0;
for(int j=1;j<=n;j++){
if(j<a[i]) e[i][j]=e[i-1][j];
else e[i][j]=max(e[i-1][j],e[i-1][j-a[i]]+b[i]);
}
}
cout<<e[m][n];
}
一维优化版,更省空间
用一维dp数组,从后往前填,避免覆盖:
int dp[101]={0};
for(int i=1;i<=m;i++){
for(int j=n;j>=a[i];j--){
dp[j]=max(dp[j],dp[j-a[i]]+b[i]);
}
}
cout<<dp[n];<<endl;
这才是标准01背包,n是容量,m物品数,a重量,b价值。
调试建议
输出dp表看过程:for(int j=0;j<=n;j++) cout<<dp[j]<<' '; 多跑小数据验证,比如n=5 m=2,物品(2,3)(3,4),答案应是7。
常见坑点
1.数组下标从0还是1,统一用1~m。2.容量j从0到n都要设dp[0]=0。3.01背包必须反向循环,否则变成完全背包。4.输入n是容量m物品数,对吧?
FAQ
Q: 为什么用一维数组反向循环?
A: 正向会重复用同一物品,变成无限制背包,反向确保每个物品只用一次。
Q: e[i][0]为什么设0?
A: 容量为0时价值必0。
Q: n=100 m=100会超时间吗?
A: 时间O(nm)=10^4,没问题。
Q: 怎么输出最大价值?
A: 直接cout<<e[m][n] 或 dp[n]。
Q: 负价值物品怎么办?
A: 01背包价值一般非负,不考虑。