【0-1背包复习】HDU 2602——Bone Collector

题目:点击打开链接

基本0-1背包，不解释了，注意0的时候的情况。附一组TRICK数据：

1
5 0
2 4 1 5 1
0 0 1 0 0

答案是12.

#include <iostream>#include <cstring>using namespace std;int dp[1005],value[1005],weight[1005];int main(){int testcase;cin>>testcase;while(testcase--){memset(dp,0,sizeof(dp));memset(value,0,sizeof(value));memset(weight,0,sizeof(weight));int totalsth,totalw;cin>>totalsth>>totalw;for(int i=0;i<totalsth;i++){cin>>weight[i];}for(int j=0;j<totalsth;j++){cin>>value[j];}for(int i=0;i<totalsth;i++){for(int j=totalw;j>=value[i];j--){if(dp[j]<=dp[j-value[i]]+weight[i])dp[j]=dp[j-value[i]]+weight[i];}}cout<<dp[totalw]<<endl;}return 0;}