Chinaunix首页 | 论坛 | 博客

Lzy

  • 博客访问: 215961
  • 博文数量: 56
  • 博客积分: 0
  • 博客等级: 民兵
  • 技术积分: 675
  • 用 户 组: 普通用户
  • 注册时间: 2014-02-27 15:50
文章分类

全部博文(56)

文章存档

2014年(56)

我的朋友

分类: C/C++

2014-11-23 16:52:54


点击(此处)折叠或打开

  1. #include<stdio.h>
  2. #include<string.h>
  3. #include<math.h>
  4. #include<iostream>
  5. #include <memory.h>

  6. using namespace std;
  7. int main()
  8. {
  9.     int n;
  10.     int bone;
  11.     int volume;
  12.     int i,j;
  13.     int b[1001]; // each bone's value
  14.     int v[1001];
  15.     int re[1001];
  16.     #ifdef local
  17.     freopen("in.txt","r",stdin);
  18.     #endif

  19.     scanf("%d",&n);
  20.     while(n--)
  21.     {
  22.         memset(b,0,sizeof(b));
  23.         memset(v,0,sizeof(v));
  24.         memset(re,0,sizeof(re));

  25.         scanf("%d%d",&bone,&volume);
  26.         for(i = 0; i < bone; i++)
  27.         {
  28.             scanf("%d",&b[i]);
  29.         }
  30.         for(i = 0; i < bone; i++)
  31.         {
  32.             scanf("%d",&v[i]);
  33.         }
  34.         //DP
  35.         for(i = 0; i < bone; i++)
  36.         {
  37.             for(j = volume; j-v[i]>=0; j--)
  38.             {
  39.                 re[j] = max(re[j],re[j-v[i]] + b[i]);
  40.             }
  41.         }
  42.         printf("%d\n",re[volume]);
  43.     }
  44. }

阅读(1302) | 评论(0) | 转发(0) |
给主人留下些什么吧!~~