巢穴

about:blank

P1276

还是背包..

#include <iostream>
using namespace std;
const int MAXN=11;
int cash;
int n;
int t[MAXN];
int g[MAXN];
bool f[100001];
int main()
{
 while(cin>>cash>>n)
 {
  for (int i=1;i<=n;i++)
  {
   cin>>t[i]>>g[i];
  }
  memset(f,false,sizeof(f));
  f[0]=true;
  for (int i=1;i<=n;i++)
   for (int j=cash;j>=0;j--)
   {
    if (f[j])
    {
     for (int k=1;k<=t[i];k++)
     {
      int p=j+k*g[i];
      if (p<=cash) f[p]=true;
     }
    }
   }
  for (int i=cash;i>=0;i--)
   if (f[i]) {cout<<i<<endl;break;}
 }
 
    
 return 0;
}

posted on 2009-11-05 16:04 Vincent 阅读(110) 评论(0)  编辑 收藏 引用 所属分类: 数据结构与算法


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