- 1#include 2 using namespace std;
- 3 int main() 4 {
- 5 int n;
- 6 int v[1010],
- dp[1010],
- d[1010]; //v代表体积,d代表谷歌值
- 7
- while (scanf("%d", &n) != EOF) 8 {
- 9
- while (n--) 10 {
- 11 memset(v, 0, sizeof(v));
- 12 memset(dp, 0, sizeof(dp));
- 13 memset(d, 0, sizeof(d));
- 14 int x,
- y;
- 15 cin >> x >> y;
- 16
- for (int i = 1; i <= x; i++) 17 cin >> d[i];
- 18
- for (int i = 1; i <= x; i++) 19 cin >> v[i];
- 20
- for (int i = 1; i <= x; i++) //01背包主函数
- 21 {
- 22
- for (int j = y; j >= v[i]; j--) 23 {
- 24 dp[j] = max(dp[j], dp[j - v[i]] + d[i]);
- 25
- }
- 26
- }
- 27 printf("%d\n", dp[y]);
- 28
- }
- 29
- }
- 30
- return 0;
- 31
- }
来源: http://www.bubuko.com/infodetail-2056991.html