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 ?
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.
One integer per line representing the maximum of the total value (this number will be less than 2^31).
入门级别的0-1背包问题，简直不要太简单。
#include <iostream> #include <algorithm> #include <string> #include <vector> #include <stack> #include <queue> #include <map> #include <set> #include <cstdio> #include <cstdlib> #include <cstring> #include <cmath> using namespace std; #define ll long long #define clean(arrays) memset(arrays, 0, sizeof(arrays)) int T, N, V; int v[1005], w[1005]; ll dp[1005]; int main() { cin >> T; while (T--) { clean(v); clean(w); clean(dp); cin >> N >> V; for (int i = 1; i <= N; i++) cin >> v[i]; for (int i = 1; i <= N; i++) cin >> w[i]; for (int i = 1; i <= N; i++) { for (int j = V; j >= w[i]; j--) { dp[j] = max(dp[j], dp[j - w[i]] + v[i]); } } cout << dp[V] <<endl; } return 0; }