[原]hdu2602 Bone Collector (01背包)

时间:2023-03-31 22:23:20

本文出自:http://blog.csdn.net/svitter

题意:典型到不能再典型的01背包。给了我一遍AC的快感。

//============================================================================
// Name : 2602.cpp
// Author : vit
// Version :
// Copyright : Your copyright notice
// Description : Hello World in C++, Ansi-style
//============================================================================ #include <iostream>
#include <stdio.h>
#include <string.h> using namespace std;
#define max(a, b) a > b ? a : b struct Bone{
int val;
int vol;
}; Bone b[1010];
int dp[1010]; void ace(){
//work point
int t;
int i, j ,k; //num
int n, v; cin >> t;
while(t --){
memset(dp, 0, sizeof(dp));
scanf("%d%d", &n, &v);
for(i = 0; i < n; i++){
scanf("%d", &b[i].val);
}
for(i = 0; i < n; i++){
scanf("%d", &b[i].vol);
} for(i = 0; i < n; i++)
for(j = v; j >= b[i].vol; j--){
dp[j] = max(dp[j], dp[j - b[i].vol] + b[i].val);
} printf("%d\n", dp[v]);
}
}
int main() {
ace();
return 0;
}
作者:svitter 发表于2014-5-2 16:36:37 原文链接
阅读:200 评论:0 查看评论