背包问题有好多种，那些名称也记得不太清，随便称呼吧，会做题就行，先试试4种常见的背包问题。
题目1：普通的背包问题（0-1背包）
有 n 个重量和价值分别为Wi,Vi的物品，现从这些物品中挑选出总量不超过 W 的物品，求所有方案中价值总和的最大值。
Input:
输入包含多组测试用例，每一例的开头为两位整数 n、W（1<=n<=10000,1<=W<=1000） ，接下来有 n 行，每一行有两位整数 Wi、Vi（1<=Wi<=10000,1<=Vi<=100）。
Output:
输出为一行，即所有方案中价值总和的最大值。
Sample Input:
3 4 1 2 2 5 3 7
Sample Output:
9
思路：相同容量找最大值，取和不取找最大值。
AC代码：
#include<stdio.h> #include<algorithm> #include<iostream> #include<cstring> using namespace std; int dp[10050]; int wi[10050],vi[10050]; int main() { int n,m; while(scanf("%d%d",&n,&m)!=EOF) { memset(dp,0,sizeof(dp)); ///重量，价格 for(int i=0;i<n;i++) scanf("%d%d",&wi[i],&vi[i]); for(int i=0;i<n;i++) for(int j=m;j>=wi[i];j--) dp[j]= max( dp[j], dp[ j-wi[i]]+vi[i]); printf("%d ",dp[m]); } return 0; }
模拟过程：
/* 5个物品，背包容量10 物品下标 重量w 价格v 0 3 4 1 4 5 2 7 3 3 2 6 4 1 1 dp[0] dp[1] dp[2] dp[3] dp[4] dp[5] dp[6] dp[7] dp[8] dp[9] dp[10] dp[11] 输入n=5，W=10 for(i=0;i<n;i++) i=0;i<5； /// 不放 放 取最大值 j=10; j>=w[0]=3; dp[10]=max( dp[10]=0; dp[10-3]+4)=4 j=9; j>=w[0]=3; dp[9]= max( dp[9]=0; dp[9-3]+4)=4 j=8; j>=w[0]=3; dp[8]= max( dp[8]=0; dp[8-3]+4)=4 j=7; j>=w[0]=3; dp[7]= max( dp[7]=0; dp[7-3]+4)=4 j=6; j>=w[0]=3; dp[6]= max( dp[6]=0; dp[6-3]+4)=4 j=5; j>=w[0]=3; dp[5]= max( dp[5]=0; dp[5-3]+4)=4 j=4; j>=w[0]=3; dp[4]= max( dp[4]=0; dp[4-3]+4)=4 j=3; j>=w[0]=3; dp[3]= max( dp[3]=0; dp[3-3]+4)=4 i=1;i<5; j=10; j>=w[1]=4; dp[10]=max( dp[10]=4; dp[10-4]=4+5)=9///给出10容量，不放和放取最大值 j=9; j>=w[1]=4; dp[9]=max ( dp[9]=4; dp[9-4]=4+5)=9 j=8; j>=w[1]=4; dp[8]=max ( dp[8]=4; dp[8-4]=4+5)=9 j=7; j>=w[1]=4; dp[7]=max ( dp[7]=4; dp[7-4]=4+5)=9 j=6; j>=w[1]=4; dp[6]=max ( dp[6]=4; dp[6-4]=0+5)=5///给出6容量，第一第二物品二选一，价格取最大值 j=5; j>=w[1]=4; dp[5]=max ( dp[5]=4; dp[5-4]=0+5)=5 j=4; j>=w[1]=4; dp[4]=max ( dp[4]=4; dp[4-4]=0+5)=5 i=2;i<5;///只要放得下，都找到最优解，如果放不下，不会更新记录 j=10; j>=w[2]=7; dp[10]=max( dp[10]=9; dp[10-7]=4+3)=9///一个是之前的放入12物品的最优解，比放入第三个物品价格还高 j=9; j>=w[2]=7; dp[9]=max ( dp[9]=9; dp[9-7]=0+3)=9///第二个物品7的重量，给出9容量的背包，只能放下第二个物品，价格明显不划算 j=8; j>=w[2]=7; dp[8]=max ( dp[8]=9; dp[8-7]=0+3)=9 j=7; j>=w[2]=7; dp[7]=max ( dp[7]=9; dp[7-7]=0+3)=9 i=3;i<5; j=10; j>=w[3]=2; dp[10]=max( dp[10]=9; dp[10-2]=9+6)=15///放3个物品价格最高 j=9; j>=w[3]=2; dp[9]= max( dp[9]=9; dp[9-2]=9+6)=15 j=8; j>=w[3]=2; dp[8]= max( dp[8]=9; dp[8-2]=5+6)=11///给出8容量背包，放2、4物品最优 j=7; j>=w[3]=2; dp[7]= max( dp[7]=9; dp[7-2]=5+6)=11 j=6; j>=w[3]=2; dp[6]= max( dp[6]=5; dp[6-2]=5+6)=11 j=5; j>=w[3]=2; dp[5]= max( dp[5]=5; dp[5-2]=4+6)=10///给出5容量背包，放1、4物品最优 j=4; j>=w[3]=2; dp[4]= max( dp[4]=5; dp[4-2]=0+6)=6///以下除了放4物品，其他都放不下 j=3; j>=w[3]=2; dp[4]= max( dp[3]=4; dp[4-2]=0+6)=6 j=2; j>=w[3]=2; dp[4]= max( dp[2]=0; dp[2-2]=0+6)=6 i=4;i<5; j=10; j>=w[4]=1; dp[10]=max( dp[10]=15; dp[10-1]=15+1)=16; j=9; j>=w[4]=1; dp[9]= max( dp[9]=15; dp[9-1]=11+1)=15; j=8; j>=w[4]=1; dp[8]= max( dp[8]=11; dp[8-1]=11+1)=12; j=7; j>=w[4]=1; dp[7]= max( dp[7]=11; dp[7-1]=11+1)=12; j=6; j>=w[4]=1; dp[6]= max( dp[6]=11; dp[6-1]=11+1)=12; j=5; j>=w[4]=1; dp[5]= max( dp[5]=10; dp[5-1]=10+1)=11; j=4; j>=w[4]=1; dp[4]= max( dp[4]=6; dp[4-1]=6+1)=7; j=3; j>=w[4]=1; dp[3]= max( dp[3]=6; dp[3-1]=6+1)=7; j=2; j>=w[4]=1; dp[2]= max( dp[2]=6; dp[2-1]=0+1)=6; j=1; j>=w[4]=1; dp[1]= max( dp[1]=6; dp[1-1]=0+1)=1; */
题目2：总和恰好是背包重量的问题，完全背包？
有 n 个重量和价值分别为Wi,Vi的物品，现从这些物品中挑选出总量刚好为 W 的物品 ，求所有方案中价值总和的最大值。
Input:
输入包含多组测试用例，每一例的开头为两位整数 n、W（1<=n<=10000,1<=W<=1000） ，接下来有 n 行，每一行有两位整数 Wi、Vi（1<=Wi<=10000,1<=Vi<=100）。
Output:
输出为一行，即所有方案中价值总和的最大值。若不存在刚好填满的情况，输出“-1”。
Sample Input:
3 4 1 2 2 5 2 1 3 4 1 2 2 5 5 1
Sample Output:
6 -1
AC代码：
#include<stdio.h> #include<algorithm> #include<iostream> #include<cstring> using namespace std; int dp[10050];///下标是背包容量， int wi[10050],vi[10050]; int main() { int n,m; while(scanf("%d%d",&n,&m)!=EOF) { memset(dp,-1,sizeof(dp)); dp[0]=0; ///重量，价格 for(int i=0;i<n;i++) scanf("%d%d",&wi[i],&vi[i]); for(int i=0;i<n;i++) for(int j=m;j>=wi[i];j--)///从最大重量开始找 if(dp[ j-wi[i] ]!=-1) ///一开始除了dp[0]外都是-1，如果j-wi[i]=0,证明把背包放满了， dp[j]= max( dp[j], dp[ j-wi[i]]+vi[i]); printf("%d ",dp[m]); ///最后直接输出背包重量为m的情况就行。 } return 0; }
模拟过程：
5个物品，背包容量10 物品下标 重量w 价格v 0 3 4 1 4 5 2 3 3 3 2 6 4 2 4 { memset(dp,-1,sizeof(dp)); for i=0;i<n;i++ for从m到小找到能放满的情况即j-wi[0]=0的情况 ... dp[3]=max(dp[3]=-1,dp[3-3]+4=0+4=4)=4; //放入3重量后的最大价格 i=1;i<n; 找到j-wi[1]=0或3的情况 ... dp[7]=max(dp[7]=-1,dp[7-4]+5=4+5=9)=9; //放入7重量后的最大价格，目前是第一和第二物品的总价格 ... dp[4]=max(dp[4]=-1,dp[4-4]+5=0+5=5)=5; //放入3重量后的最大价格 i=2;i<n; 找到j-wi[2]=0或3或7或4的情况 dp[10]=max(dp[10]=-1,dp[10-7]+3=9+3=12)=12; ///放入10重量后的最大价格，目前是前三个物品的总价格 ... dp[7]=max(dp[7]=9,dp[7-3]=5+3=8)=9;///放入7重量后的最大价格，第一物品+第二物品vs第一物品+第三物品，明显前者价格大 dp[6]=max(dp[6]=-1,dp[6-3]=4+3=7)=7;/////放入6重量后的最大价格，目前是第一和第三物品的总价格 ... dp[3]=max(dp[3]=4,dp[3-3]=0+3=3)=4;///放入3重量后的最大价格，第一物品vs第三物品，明显前者价格大 i=3;i<n; 找到 dp[ j-wi[i] ]!=-1 的情况 ... dp[9]=max(dp[9]=-1,dp[9-2]=9+6=15)=15;///1+2+4 dp[8]=max(dp[8]=-1,dp[8-2]=7+6=13)=13;///1+3+4 ... dp[6]=max(dp[6]=7,dp[6-2]=5+6=11)=11;///1+3 vs 2+4 后者价格大 dp[5]=max(dp[5]=-1,dp[5-2]=4+6=10)=10;///1+4不需要和3+4比较了，之前放入三重量的最优解就是放入第一物品 ... dp[2]=max(dp[2]=-1,dp[2-2]=0+6=6)=6;///4 ... i=4;i<5; 找到 dp[ j-wi[i] ]!=-1 的情况 dp[10]=max(dp[10]=12,dp[10-2]=13+4=17)=17; ///1+2+3 vs 1+3+5 dp[9]=max(dp[9]=15;dp[9-2]=9+4=13)=13; ///1+2+4 vs 1+2+5 dp[8]=max(dp[8]=13;dp[8-2]=11+4=15)=15; ///1+3+4 vs 1+3+5 dp[7]=max(dp[7]=9;dp[7-2]=10+4=14)=14; ///1+3 vs 1+4+5 dp[6]=max(dp[6]=11;dp[6-2]=5+4=9)=11; ///1+3 vs 2+5 dp[5]=max(dp[5]=10;dp[5-2]=4+4=8)=10; ///1+4 vs 1+5 dp[4]=max(dp[4]=5;dp[4-2]=6+4=10)=10; /// 2 vs 4+5 dp[2]=max(dp[2]=6;dp[2-2]=0+4=4)=6; /// 4 vs 5 break; }
题目3：可以取的物品有无限个，无限背包？
有 n 种（每一种有无数个）重量和价值分别为Wi,Vi的物品，现从这些物品中挑选出总 量不超过 W 的物品，求所有方案中价值总和的最大值。
Input:
输入包含多组测试用例，每一例的开头为两位整数 n、W（1<=n<=10000,1<=W<=1000） ，接下来有 n 行，每一行有两位整数 Wi、Vi（1<=Wi<=10000,1<=Vi<=100）
Output:
输出为一行，即所有方案中价值总和的最大值。
Sample Input:
3 4 1 2 2 5 3 7 3 5 2 3 3 4 4 5
Sample Output:
10 7
AC代码：
#include<stdio.h> #include<algorithm> #include<iostream> #include<cstring> using namespace std; int dp[10005]; int w[10005],v[10005];///重量，价格 int main()///1133 { int n,m;///物品数，背包重量 while(scanf("%d%d",&n,&m)!=EOF) { memset(dp,0,sizeof(dp)); for(int i=0;i<n;i++) scanf("%d%d",&w[i],&v[i]); for(int i=0;i<n;i++) for(int j=w[i];j<=m;j++)///从物品的大小开始，只要你放得下，随便放，取最大值 dp[j]=max(dp[j],dp[ j-w[i] ]+v[i] ); printf("%d ",dp[m]); } return 0; }
题目4：变相普通背包？
有 n 个重量和价值分别为Wi,Vi的物品，现从这些物品中挑选出总量不超过 W 的物品，求所有方案中价值总和的最大值。
Input:
输入包含多组测试用例，每一例的开头为两位整数 n、W;接下来有 n 行，每一行有两位整数 Wi、Vi 其中： 1<=n<=100 1<=W<=1000,000,000 1<=Wi<=10,000,000 1<=Vi<=100。
Output:
输出为一行，即所有方案中价值总和的最大值。
Sample Input:
4 5 2 3 1 2 3 4 2 2 4 10000000 2 3 2 2 3 3 1 2
Sample Output:
7 10
思路：用第一种方法明显爆时间，我们可以看到物品价格是比较小的，转换一下思路，相同的价格取总重量最小的物品
AC代码：
#include<iostream> #include<cstring> #include<stdio.h> #include<bits/stdc++.h> using namespace std; const int inf=1111111111; ///dp下标存放价格，内容存放重量 int dp[10005]; int main() { int n,m;/// while( scanf("%d%d", &n,&m)!=EOF) { for(int i=0;i<10005;i++) dp[i]=inf;///重量巨大，取重量小的，自然就把这些筛掉 dp[0]=0; int w[n],v[n]; for(int i=0;i<n;i++) scanf("%d%d",&w[i],&v[i]);///重量，价格 for(int i=0;i<n;i++) for(int j=10004;j>=v[i];j--)///最高价格 = 数量*物品单价 再多一些 if( dp[ j-v[i] ]!=inf && dp[ j-v[i] ]+w[i]<=m ) ///重量从0开始取，并且放下这个物品后 重量比背包重量小 dp[j] = min( dp[j], dp[ j-v[i] ]+w[i] ); ///相同的价格，取重量最小 for(int j=10004; j>=0; j--) if( dp[j]!=inf ) ///只要重量不是无穷，那么就是有东西的，第一个撞见的就是价格最大的 {printf("%d ",j);break;} } return 0; }