【杭电0j2602】Bone Collector

柔光的暖阳◎ 2022-07-19 05:12 44阅读 0赞

# Bone Collector #

**Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)  
Total Submission(s): 51528 Accepted Submission(s): 21697**

Problem Description

Many years ago , in Teddy’s hometown there was a man who was called “Bone Collector”. This man like to collect varies of bones , such as dog’s , cow’s , also he went to the grave …  
The bone collector had a big bag with a volume of V ,and along his trip of collecting there are a lot of bones , obviously , different bone has different value and different volume, now given the each bone’s value along his trip , can you calculate out the maximum of the total value the bone collector can get ?  
![C154-1003-1.jpg][]

Input

The first line contain a integer T , the number of cases.  
Followed by T cases , each case three lines , the first line contain two integer N , V, (N <= 1000 , V <= 1000 )representing the number of bones and the volume of his bag. And the second line contain N integers representing the value of each bone. The third line contain N integers representing the volume of each bone.

Output

One integer per line representing the maximum of the total value (this number will be less than 2 31).

Sample Input

1
    5 10
    1 2 3 4 5
    5 4 3 2 1

Sample Output

Author

Teddy

Source

[HDU 1st “Vegetable-Birds Cup” Programming Open Contest ][HDU 1st _Vegetable-Birds Cup_ Programming Open Contest]

Recommend

lcy | We have carefully selected several similar problems for you: [1203][] [2159][] [2955][] [1171][] [2191][]

#include<cstdio>
    #include<cstring>
    #include<algorithm>
    using namespace std;
    const int N = 1002;
    int val[N],vol[N],dp[N];
    int main() {
    	int T;
    	scanf("%d",&T);
    	while(T--) {
    		int n,V;
    		memset(dp,0,sizeof(dp));
    		scanf("%d%d",&n,&V);
    		for(int i=1; i<=n; i++) scanf("%d",&val[i]);
    		for(int j=1; j<=n; j++) scanf("%d",&vol[j]);
    		for(int i=1; i<=n; i++) {
    			for(int j=V; j>=vol[i]; j--) {			//倒序，关键 
    				if(dp[j-vol[i]]+val[i]>dp[j]) {		//正序的话会使上一个i被忽略 
    					dp[j]=dp[j-vol[i]]+val[i];
    				}
    			}
    		}
    		printf("%d\n",dp[V]);
    	}
    	return 0;
    }

[题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=2602][http_acm.hdu.edu.cn_showproblem.php_pid_2602]

[C154-1003-1.jpg]: /images/20220718/12bf65dbe1254cb1994fbabb4b285387.png
[HDU 1st _Vegetable-Birds Cup_ Programming Open Contest]: http://acm.hdu.edu.cn/search.php?field=problem&key=HDU+1st+%A1%B0Vegetable-Birds+Cup%A1%B1+Programming+Open+Contest&source=1&searchmode=source
[1203]: http://acm.hdu.edu.cn/showproblem.php?pid=1203
[2159]: http://acm.hdu.edu.cn/showproblem.php?pid=2159
[2955]: http://acm.hdu.edu.cn/showproblem.php?pid=2955
[1171]: http://acm.hdu.edu.cn/showproblem.php?pid=1171
[2191]: http://acm.hdu.edu.cn/showproblem.php?pid=2191
[http_acm.hdu.edu.cn_showproblem.php_pid_2602]: http://acm.hdu.edu.cn/showproblem.php?pid=2602