#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 13:49:30 浏览: 20
这段代码是求解 01 背包问题的,具体问题不在此赘述。代码本身存在两个问题:
1. 数组越界问题:在输入物品重量和价值时,数组下标应该从 0 开始,而不是从 1 开始。因此应该改为:
```
for(i=0;i<n;i++){
cin>>w[i];
}
for(i=0;i<n;i++){
cin>>p[i];
}
```
2. 取最大值时应该考虑不选择当前物品的情况:在取当前物品时,应该比较选择当前物品和不选择当前物品的价值,取最大值。因此,应该将计算最大价值的代码改为:
```
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];
}
```
这样修改后,代码应该是正确的。
相关问题
#include <iostream> #include <cstdio> #include <cstdlib> #include <algorithm> #include <cstring> #include <stack> #include <ctime> 怎么配置这些文件
这些文件是C++的头文件,不需要配置。在编写C++程序时,只需要在代码中包含这些头文件即可使用它们提供的函数和类。这些头文件一般都已经被安装在你的C++编译器中了,你只需要在代码中添加`#include`指令即可。比如,如果你想使用`iostream`头文件中的`cout`和`cin`,你可以这样写代码:
```
#include <iostream>
using namespace std;
int main(){
cout<<"Hello World"<<endl;
return 0;
}
```
如果你使用的是Visual Studio等IDE,一般会自动帮你添加这些头文件,你只需要专注于代码的编写即可。
优化这段代码#include <iostream> #include <vector> #include <string> using namespace std; int main() { string s; s.reserve(100); char c; while (cin >> c) { s.push_back(c); } cout << "s===" << s << endl; return 0; }
这段代码的主要问题在于使用了大量的string操作,如果输入的数据量很大,会导致效率较低。可以使用字符数组来代替string,同时减少vector的使用,代码如下:
```c++
#include <iostream>
#include <cstring>
using namespace std;
int main() {
char s[100];
int len = 0;
char c;
while (cin >> c) {
s[len++] = c;
}
s[len] = '\0';
cout << "s===" << s << endl;
return 0;
}
```
这里使用了字符数组s来存储输入的字符,同时使用一个变量len来记录当前字符数组中已经存储的字符数。当输入一个字符时,将其存入字符数组s中,并将len加1。最后,将字符数组s的最后一个字符设置为'\0',以便输出时正确显示字符串。这样可以避免使用string的大量操作,从而提高了效率。