HDU 2602 Bone Collector

http://acm.hdu.edu.cn/showproblem.php?pid=2602

水题一道，依旧是0/1背包的问题。。。加深理解O(∩_∩)O~

View Code

 1 #include <iostream>
 2 #define maxn 1005
 3 using namespace std;
 4 long ans[maxn], v[maxn], w[maxn];
 5 int main()
 6 {
 7     long t, n, m, i,j;
 8     cin >> t;
 9     while(t--)
10     {
11         cin >> n >> m;
12         for(i = 0; i < n; i++)
13         cin >> w[i];
14         for(i = 0; i < n; i++)
15         cin >> v[i];
16         for(i = 0; i <= m; i++)
17         ans[i] = 0;
18         for(i = 0; i < n; i++)
19         for(j = m; j >= v[i]; j--)
20         if(ans[j-v[i]] + w[i] > ans[j])
21           ans[j] = ans[j-v[i]]+w[i];
22         cout << ans[m]<< endl;  
23     }
24     return 0;
25 }