讨论 / 10行C++程序50分,5分线上,哪里错了啊!
892611452 2012-01-19 14:34:00
点我顶贴 收藏 删除
#include<iostream>

using namespace std;

int n,c,w[5001],v[5001],b[10001];

int main()

{ cin>>n>>c;for(int i=1;i<=n;i++)cin>>w[i]>>v[i];

for(int i=1;i<=n;i++)

for(int j=w[i];j<=c;j++)

b[j]=max(b[j],b[j-w[i]]+v[i]);

cout<<b[c]<<endl;

return 0;}

#1 怡红公子@2012-01-16 16:19:00
回复 删除
建议LZ将b[]的初始值定为-10000

ok.

数据里面有负数。

给分

#2 wh3z_wsc@2012-01-19 14:34:00
回复 删除
简单的完全背包!

#include<iostream>

using namespace std;

int max(int a,int b){

return a>b?a:b;}

int main(){

int i,j,f[10010],n,m,a[5010],b[5010];

cin>>n>>m;

for(i=1;i<=n;i++)cin>>a[i]>>b[i];

for(i=1;i<=m;i++)f[i]=-50000;//初始值

f[0]=0;

for(i=1;i<=n;i++)

for(j=a[i];j<=m;j++)

f[j]=max(f[j],f[j-a[i]]+b[i]);

cout<<f[m]<<endl;

}

查看更多回复
提交回复