Multiplepack coming~^.^

时间：2022-03-26 09:54:05

多重背包：

基本思路：

先来看一个引例：有N种物品和一个容量为V的背包。第i种物品最多有n[i]件可用，每件费用是c[i]，价值是w[i]。求解将哪些物品装入背包可使这些物品的费用总和不超过背包容量，且价值总和最大。这种类型的背包问题的特点是：每件物品的件数有限。

和完全背包问题很类似。基本的方程只需将完全背包问题的方程略微一改即可，因为对于第i种物品有n[i]+1种策略：取0件，取1件„„取n[i]件。令f[i][v]表示前i种物品恰放入一个容量为v的背包的最大权值，则有状态转移方程：f[i][v]=max{f[i-1][v-k*c[i]]+k*w[i]|0<=k<=n[i]} 完全背包中k的范围是（0<=k<=v/c[i]）. 复杂度是O(V*Σn[i]),

代码与完全背包的区别仅在内部循环上由

1
for(k = 1; k <= j/weight[i]; ++k)

变为

1
for(k = 1; k <=n[i] && k<=j/weight[i]; ++k)

多重背包二进制拆分实现

跟完全背包一样的道理，利用二进制的思想将n[i]件物品i拆分成若干件物品，目的是在0-n[i]中的任何数字都能用这若干件物品代换，另外，超过n[i]件的策略是不允许的。

方法是将物品i分成若干件，其中每一件物品都有一个系数，这件物品的费用和价值都是原来的费用和价值乘以这个系数，使得这些系数分别为1,2,4,…,2^(k-1),n[i]-2^k+1，且k满足n[i]-2^k+1>0的最大整数。例如，n[i]=13，就将该物品拆成系数为1、2、4、6的四件物品。分成的这几件物品的系数和为n[i]，表明不可能取多于n[i]件的第i种物品。另外这种方法也能保证对于0..n[i]间的每一个整数，均可以用若干个系数的和表示。

 #include <iostream>

 using namespace std;

 /* 多重背包 二进制拆分

  * Time Complexity  大于O(N*V)

  * Space Complexity O(N*V)

  * 设 V <= 200 N <= 10 ，拆分后 物品总数 < 50

  * 每件物品有 log n[i]种状态

  */

 int maxV[];

 int weight[]; /* 记录拆分后物体重量 */

 int value[];  /* 记录拆分后物体价值 */

 int V, N;

 void main()

 {

     int i, j;

     scanf("%d %d",&V, &N);

     int weig, val, num;

     int count = ;

     for(i = ; i < N; ++i)

     {

         scanf("%d %d %d",&weig,&val,&num);

         for(j = ; j <= num; j <= ) // 二进制拆分

         {

             weight[count] = j * weig;

             value[count++] = j * val;

             num -= j;

         }

         if(num > )

         {

             weight[count] = num * weig;

             value[count++] = num * val;

         }

     }

     for(i = ; i < count; ++i)  // 使用01背包

     {

         for(j = V; j >= weight[i]; --j)

         {

             int tmp = maxV[j-weight[i]] + value[i];

             maxV[j] = maxV[j] > tmp ? maxV[j] : tmp;

         }

     }

     printf("%d",maxV[V]);

 }

 /*

     【输入样例】

     4 20

     3     9     3

     5     9     1

     9     4     2

     8     1     3

     【输出样例】

     47

 */

下面给出O(log amount)时间处理一件多重背包中物品的过程，其中amount表示物品的数量：

 void multiplepack(int cost, int weight, int amount)

 {

     if(cost*amount>=V)

         cmpletepack(cost,weight);

     else

     {

         int k=;

         while(k<amount)

         {

             zeroonepack(k*cost,k*weight);

             amount-= k;

             k=k*;

         }

         zeroonepack(amount*cost,amount*weight);

     }

 }

总结完啦~要回家了已经做不进去题了~噶呜~但我还在坚持每天更新博客~*。*

随机推荐

  1. SQL 变量

    1.变量可以暂时储存数据 --定义变量:  declare @xxx int --变量赋值:  set @xxx=1  select @xxx=3 --变量的使用:  print @xxx 2.--全 ...

  2. innerHTML&period;&period;innerText&period;&period;textContent

    /* * innerText和textContent 都是设置文字内容的,如果设置的内容当中有标签,也会直接的以文本的方式显示(标签的<>都会按照转义的方式进行解析) * innerTex ...

  3. 15条变量&amp&semi;方法命名的最佳实践【转】

    原文地址:15 Best Practices of Variable & Method Naming 不同的代码段采用不同的命名长度.通常来说,循环计数器(loop counters)采用1位 ...

  4. 网站瓶颈分析—MYSQL性能分析

    一.关于慢查询设置和分析 查找慢查询参数 mysql> show variables like 'long%'; +-----------------+----------+ | Variabl ...

  5. C 【block类型全方位详解】

    ------------------------------------------- block变量的概念 #import <Foundation/Foundation.h> int m ...

  6. 《BackboneJS框架的技巧及模式》&lpar;4&rpar;完结篇

    <BackboneJS框架的技巧及模式>(4)完结篇 本文紧接第二部分:<BackboneJS框架的技巧及模式(3)> 作者:chszs,转载需注明.博客主页:http://b ...

  7. 我的Pandas应用场景（2）

    上文交代了一些啰嗦事,本文开始,就要来点实际的了. 先来一个比较简单的场景: Given:一个包括N(极其复杂,这里取3个)个列的DataFrame:df,df包括index: And:对df所有列元 ...

  8. mysql解决中文乱码问题

    安装文件 my.ini default-character-set=gbk 安装文件 db.opt default-character-set=gbkdefault-collation=gbk_chi ...

  9. Maven原型骨架及常见问题

    关于Maven原型工程的制作就不在这里详细介绍了,具体细节请参考之前的文章:定制Maven原型生成项目 下面分享制作和使用Maven原型工程时碰到的常见问题,以及原型的上传和使用方法. 1.模块路径问 ...

  10. 巧用FineReport搭建成本管控监测系统

    一.应用背景 企业在近几年快速发展,规模也越来越大,而信息传递与反馈手段却仍然比较落后,随着信息技术的不断发展,人们开始通过尝试利用技术手段改善这种环境.企业的项目不断增多,而作为高层管理者,通过层级 ...

相关文章