01 背包
有n 种不同的物品，每个物品有两个属性，size 体积，value 价值，每种物品只有一个，现在给一个容量为 w 的背包，问最多可带走多少价值的物品。
1 int f[w+1]; //f[x] 表示背包容量为x 时的最大价值
2 for (int i=0; i 3 for (int j=w; j>=size[i]; j--) 4 f[j] = max(f[j], f[j-size[i]]+value[i]); //逆序 完全背包 如果物品不计件数，就是每个物品有无数件的话，稍微改下即可 1 for (int i=0; i 2 for (int j=size[i]; j<=w; j++) 3 f[j] = max(f[j], f[j-size[i]]+value[i]); //正序 多重背包既是每个物体有一定的重量w和价值v，并且有一定的数量cnt,设m为背包可包含重量； 1 #include 2 #include 3 #include 4 #include 5 #include 6 #include 7 #include 8 #include 9 #include 10 using namespace std; 11 int n,m,a[105],num[105],dp[100005]; 12 void comdp(int w,int v) 13 { 14 int i; 15 for(i=w; i<=m; i++) 16 dp[i]=max(dp[i],dp[i-w]+v); 17 } 18 void zeroone(int w,int v) 19 { 20 int i; 21 for(i=m; i>=w; i--) 22 dp[i]=max(dp[i],dp[i-w]+v); 23 } 24 void multidp(int w,int v,int cnt)//此时开始多重背包，dp[i]表示背包中重量为i时所包含的最大价值 25 { 26 if(cnt*w>=m)//此时相当于物品数量无限进行完全背包 27 { 28 comdp(w,v); 29 return; 30 } 31 int k=1;//否则进行01背包转化，具体由代码下数学定理可得 32 while(k<=cnt) 33 { 34 zeroone(k*w,k*v); 35 cnt-=k; 36 k*=2; 37 } 38 zeroone(cnt*w,cnt*v); 39 return ; 40 } 定理：一个正整数n可以被分解成1,2,4,…,2^(k-1),n-2^k+1（k是满足n-2^k+1>0的最大整数）的形式，且1～n之内的所有整数均可以唯一表示成1,2,4,…,2^(k-1),n-2^k+1中某几个数的和的形式。 证明如下： （1） 数列1,2,4,…,2^(k-1),n-2^k+1中所有元素的和为n，所以若干元素的和的范围为：[1, n]； （2）如果正整数t<= 2^k – 1,则t一定能用1,2,4,…,2^(k-1)中某几个数的和表示，这个很容易证明：我们把t的二进制表示写出来，很明显，t可以表示成n=a0*2^0+a1*2^1+…+ak*2^（k-1），其中ak=0或者1，表示t的第ak位二进制数为0或者1. （3）如果t>=2^k,设s=n-2^k+1，则t-s<=2^k-1，因而t-s可以表示成1,2,4,…,2^(k-1)中某几个数的和的形式，进而t可以表示成1,2,4,…,2^(k-1)，s中某几个数的和（加数中一定含有s）的形式。 （证毕！） 相关文章
发表评论