01背包問題。
以下是我的代碼：
#include<stdio.h>
#define max(a,b) (a>b?a:b)
int main()
{
freopen("happy.in","r",stdin);
freopen("happy.out","w",stdout);
long N,m,i,j,ans=0,w[26],c[26],d[30001]={0};
scanf("%ld%ld",&N,&m);
for(i=1;i<=m;i++)
{
scanf("%ld%ld",&c[i],&w[i]);
w[i]*=c[i];
}
for(i=1;i<=m;i++)
for(j=N;j>=c[i];j--)
{
d[j]=max(d[j],d[j-c[i]]+w[i]);
ans=max(ans,d[j]);
}
printf("%ld\n",ans);
return 0;
}
posted on 2010-01-06 19:52
lee1r 閱讀(397)
評論(0) 編輯 收藏 引用 所屬分類:
題目分類：動態(tài)規(guī)劃