巢穴

about:blank

P1837

背包..
wa了一次,因为漏了物品的个数..所以数组申小了..
#include <iostream>
using namespace std;

int f[21][32*25*20+1];
int mid=16*25*20;
int n,m;
int t[21];
int g[21];
int main()
{
 cin>>n>>m;
 for (int i=1;i<=n;i++)
 {
  cin>>t[i];
 }
 for (int i=1;i<=m;i++)
 {
  cin>>g[i];
 }
 
 memset(f,0,sizeof(f));
 for (int i=1;i<=n;i++)
 {
  f[1][t[i]*g[1]+mid]++;
 }
 
 for (int i=2;i<=m;i++)
 {
  for (int j=1;j<=n;j++)
  {
   for (int k=0;k<=32*25*20;k++)
   {
    if (f[i-1][k]==0) continue;
    f[i][k+g[i]*t[j]]+=f[i-1][k];
   }
  
  }
 } 
 cout<<f[m][mid]<<endl;
 system("pause");
 return 0;
}


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


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