问题：有n个重量和价值分别为wi,vi的物品，从中挑出总质量不超过W的物品，问价值总和的最大值。
思路：对每个物品可以选择取或不取。所以状态转移方程为：dp[i][j]=max(dp[i-1][j],dp[i-1][j-wi]+vi).
核心代码：
//二维数组 dp[i][j]代表前i个物品重量为j时的最大价值 for (i=1;i<=n;i++){ for (j=W;j>=w[i];j--){ dp[i][W]=max(dp[i-1][j],dp[i-1][j-w[i]]+v[i]); } } //一维数组<span style="white-space:pre"> </span>dp[j]代表重量为j时物品的最大价值 for (i=1;i<=n;i++){ for (j=W;j>=w[i];j--) dp[j]=max(dp[j],dp[j-w[i]]+v[i]); } Bone Collector
#include<cstdio> #include<cstring> #include<algorithm> using namespace std; int N,V; int w[1001]; int v[1001]; int dp[1001]; int main(){ int t,i,j; scanf ("%d",&t); while (t--){ scanf ("%d %d",&N,&V); for (i=1;i<=N;i++) scanf ("%d",&v[i]); for (j=1;j<=N;j++) scanf ("%d",&w[j]); memset (dp,0,sizeof(dp)); for (i=1;i<=N;i++){ for (j=V;j>=w[i];j--) dp[j]=max(dp[j],dp[j-w[i]]+v[i]); } printf ("%d\n",dp[V]); } return 0; }
01背包2：
问题：同上，当限制条件较大时，如W<=10^9,vi<=100,wi<=10^7.
思路：此时重量的范围较大，价值的范围较小，所以可以改变dp对象，对不同的价值计算最小重量。
dp[i][j]代表从前i个物品中挑选价值总和为j时总重量的最小值。 状态转移方程为 dp[i][j]=min(dp[i-1][j],dp[i-1][j-v[i]+w[i]).
又见01背包
#include<cstdio> #include<cstring> #include<algorithm> #define INF 0x3f3f3f3f using namespace std; int main(){ int n,W; int i,j; int w[105],v[105]; int dp[100005]; while (scanf ("%d %d",&n,&W)!=EOF){ int sum=0; fill (dp,dp+100005,INF); dp[0]=0; for (i=0;i<n;i++){ scanf ("%d %d",&w[i],&v[i]); sum+=v[i]; } for (i=0;i<n;i++){ for (j=sum;j>=v[i];j--){ dp[j]=min(dp[j],dp[j-v[i]]+w[i]); } } for (i=sum;i>=0;i--){ if (W>=dp[i]){ printf ("%d\n",i); break; } } } return 0; }
