hdu 2602Bone Collector（0/1背包）
这是最基础的背包问题，特点是：每种物品仅有一件，可以选择放或不放。
用子问题定义状态：即f[i][v]表示前i件物品恰放入一个容量为v的背包可以获得的最大价值。则其状态转移方程便是：
f[i][v]=max{f[i-1][v],f[i-1][v-c[i]]+w[i]}
#include<iostream>#include<cmath>using namespace std;int dp[1005];int w[1005],c[1005];int main(){ int i,j,n,v,t; scanf("%d",&t); while(t--) { scanf("%d%d",&n,&v); memset(dp,0,sizeof(dp)); for(i=1;i<=n;i++) scanf("%d",&w[i]); for(i=1;i<=n;i++) scanf("%d",&c[i]); for(i=1;i<=n;i++) { for(j=v;j>=c[i];j--) { dp[j]=max(dp[j],dp[j-c[i]]+w[i]); } } printf("%d\n",dp[v]); } return 0;}