#include <iostream> #include <cstring> using namespace std; int main() { int M,n; int i,j; cin>>M; //背包容量 cin>>n; //物品个数 int w[1000];//重量 int p[1000];//价值 int x[1000];//放不放 for(i=1;i<=n;i++){ cin>>w[i]; } for(i=1;i<=n;i++){ cin>>p[i]; } int m[1000][1000];//m[i][j]表示面对第i件物品,背包容量为j时,所能获得的最大价值 memset(m,0,sizeof(m)); for(i=1;i<=n;i++){ for(j=1;j<=M;j++){ if(j>=w[i]){ if(i==1){ m[i][j]=p[i]; } else { m[i][j]=max(m[i-1][j],m[i-1][j-w[i]]+p[i]); } } else { m[i][j]=m[i-1][j]; } } } /* for(i=1;i<=n;i++){ for(j=1;j<=M;j++){ cout<<m[i][j]<<' '; } cout<<endl; }*/ cout<<m[n][M]<<' '; int weight=0;//记录放入物品个数 int c=M; for(int i=n;i>1;i--){ if(m[i][c]==m[i-1][c]) x[i]=0; else{ x[i]=1; weight+=w[i]; c-=w[i]; } } x[1]=(m[1][c]>0)?1:0; if(x[1]==1)weight+=w[1]; cout<<weight; cout<<"\n"; for(i=1;i<=n;i++){ cout<<x[i]; if(i<n)cout<<' '; } return 0; }这段代码为什么有的样例是答案错误
时间: 2024-03-12 17:49:43 浏览: 13
在这段代码中,存在一个数组越界的问题,同时也存在一些细节问题。
首先是数组越界问题:在输入物品重量和价值时,数组下标应该从 0 开始,而不是从 1 开始。因此应该改为:
```
for(i=0;i<n;i++){
cin>>w[i];
}
for(i=0;i<n;i++){
cin>>p[i];
}
```
其次是细节问题:在计算放入的物品个数时,应该从 $n$ 开始倒序遍历,而不是从 $n-1$ 开始,因为最后一个物品(即 $x_n$)的放置情况需要特别考虑。同时,当 $m[1][c]>0$ 时,$x_1$ 应该为 1,表示放入第一个物品;否则 $x_1$ 应该为 0,表示不放入第一个物品。因此,需要将计算放入的物品个数的代码改为:
```
int weight=0;//记录放入物品个数
int c=M;
for(int i=n;i>1;i--){
if(m[i][c]==m[i-1][c]){
x[i]=0;
} else {
x[i]=1;
weight+=w[i];
c-=w[i];
}
}
x[1]=(m[1][c]>0)?1:0;
if(x[1]==1){
weight+=w[1];
}
```
最后是一个小细节:输出 $x_i$ 时,应该在每个数字后面输出一个空格,以符合题目的输出格式。因此,需要将输出 $x_i$ 的代码改为:
```
for(i=1;i<=n;i++){
cout<<x[i];
if(i<n){
cout<<' ';
}
}
```
经过以上修改,代码应该就能够正确地通过测试了。