心如止水
Je n'ai pas le temps
posts - 400,comments - 130,trackbacks - 0

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 阅读(382) 评论(0)  编辑 收藏 引用 所属分类: 题目分类:动态规划

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理