Bone CollectorTime Limit:1000MS Memory Limit:32768KB 64bit IO Format:%I64d & %I64u

SubmitStatusPracticeHDU 2602

Description

Many years ago , in Teddys hometown there was a man who was called Bone Collector. This man like to collect varies of bones , such as dogs , cows , 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 bones value along his trip , can you calculate out the maximum of the total value the bone collector can get ?

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 231).
Sample Input
1 5 10 1 2 3 4 5 5 4 3 2 1
Sample Output
14

^{?}Download sourceCode.cpp

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 | #include <cstring> #include <cstdio> #include <cstring> #include <iostream> using namespace std; int main(){ int N, V, v, i; long long val[1010], c[1010], ans[1010]; int t; cin >> t; while(t --){ cin >> N >> V; memset(val, 0, sizeof(val)); memset(c, 0, sizeof(c)); memset(ans, 0, sizeof(ans)); for(i = 1; i <= N; i ++) scanf("%I64d", &val[i]); for(i = 1; i <= N; i ++) scanf("%I64d", &c[i]); for(i=1; i <= N; i ++){ for(v = V; v >= c[i]; v--){ ans[v] = max (ans[v], ans[v-c[i]] + val[i]); } } cout << ans[V] << endl; } return 0; } |

texttexttext`code`

more code

~~~~