01背包问题运行结果不对,哪里错了
问题描述:
#include
using namespace std;
const int MAXN=1005;
int v[MAXN];//物品体积
int w[MAXN];//物品价值
int dp[MAXN][MAXN];//最大价值
void main(){
int m,n,i,j;
cin>>m>>n;
for(i=1;i<=m;i++){
cin>>v[i]>>w[i];
}for(j=0;j<=n;j++){
dp[0][j]=0;}//初始化物品为0的价值为0
for(i=1;i<=m;i++){
for(j=0;j<=n;j++){
if(v[i]>j){
dp[i][j]=dp[i-1][j];//放不了第i个物品
}else
dp[i][j]=max(dp[i-1][j],dp[i-1][j-v[i]]+w[i]);//放得了第i个物品
}}
cout<<dp[i][j]<<endl;
}
int max(int a,int b){
if(a>b)
return a;
else return b;
}
答
cout<<dp[m][n]<<endl;