背包模板（转）-白红宇

背包模板（转）

阅读量：4886 次

发布时间：2019-06-11

本文共 1566 字，大约阅读时间需要 5 分钟。

01 背包

有n 种不同的物品，每个物品有两个属性，size 体积，value 价值，每种物品只有一个，现在给一个容量为 w 的背包，问最多可带走多少价值的物品。

1 int f[w+1];   //f[x] 表示背包容量为x 时的最大价值  2 for (int i=0; i
     
      =size[i]; j--)  4         f[j] = max(f[j], f[j-size[i]]+value[i]); //逆序

完全背包

如果物品不计件数，就是每个物品有无数件的话，稍微改下即可

1 for (int i=0; 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）的形式。

（证毕！）

转载于:https://www.cnblogs.com/bofengyu/p/6733207.html

你可能感兴趣的文章