背包问题系列算法详解_第1页
背包问题系列算法详解_第2页
背包问题系列算法详解_第3页
背包问题系列算法详解_第4页
全文预览已结束

下载本文档

版权说明:本文档由用户提供并上传,收益归属内容提供方,若内容存在侵权,请进行举报或认领

文档简介

1、背包问题系列算法详解背包问题是一个关于最优解的经典问题。通常被讨论的最多的,最经典的背包问题是0-1背包问题(0-1 Knapsack Problem)o它是一切背包问题及相关背包问题的基础。本篇博文将详 细分析0-1背包问题,并给出 0-1背包问题的几种解法,同时也对0-1背包问题的内涵进行延伸,丰富其外延至完全背包问题和多重背包问题,并给出背包问题的算法实现过程,希望对大家有帮助。一、0-1背包问题有N件物品和一个容量为V的背包。第i件物品(每个物品只有一件)的费用是ci,价值是wi。求解将哪些物品装入背包可使价值总和最大。(1)递归求解算法如下:#include iostream#def

2、ine CAPACITY 10#define GOODSNUM 6using namespace std;int nVolGOODSNUM;int nValueGOODSNUM;int knapsack(int itemIndex,int vol);void main() int i=0,j=0; while(iGOODSNUM) coutinput the i+1nVolinValuei;i+;coutThe max value is: knapsack(GOODSNUM,CAPACITY)=nVolitemIndex&knapsack(itemIndex-1,vol)knapsack(it

3、emIndex-1,vol-nVolitemIndex)+nValueitemIndex)return knapsack(itemIndex-1,vol-nVolitemIndex)+nValueitemIndex; elsereturn knapsack(itemIndex-1,vol);)分析:递归求解,求解过程中的绝大部分变量存在重复求解的过程,算法的效率较低,有待改进;那怎么改进呢?最有效的是用数组保存每次计算的结果,不用重复计算,于是有二维数组求解。(2)二维数组求解 算法如下:#include iostream#define CAPACITY 10#define GOODSNUM

4、6 using namespace std; void main() int i=1,j;int vGOODSNUM = 10,12,40,40,40,15;int cGOODSNUM = 1,2,3,5,2,1;int funGOODSNUM+1CAPACITY+1;for (i=1;i=GOODSNUM;i+) funi0 = 0;for (i=1;i=CAPACITY;i+) fun0i = 0;for (i=1;i=GOODSNUM;i+)for (j=1;j=CAPACITY;j+)if (jci-1)funij = funi-1j;else if (funi-1jfuni-1j-c

5、i-1 + vi-1) funij = funi-1j-ci-1 + vi-1;elsefunij = funi-1j;coutThe max value is: funGOODSNUMCAPACITYendl;分析:二维数组求解方法相比递归求解要优越很多,但是其空间复杂度依然较高,还有 继续改进的余地吗? 一维数组是否可行呢?答案是肯定的(3) 一维数组求解 算法分析:#include iostream#define CAPACITY 10#define GOODSNUM 6 using namespace std; void main()int nVolumeGOODSNUM = 1,2,

6、3,5,2,1;int nValueGOODSNUM = 10,12,40,40,40,15;int selectTableGOODSNUMCAPACITY+1 = 0;int nKnapsackCAPACITY+1 = 0;most important for the first compution below int itemIndex,capIndex;for (itemIndex=0;itemIndex=nVolumeitemIndex;capIndex-)noticethatcapIndex=nVolumeitemIndex,not capIndex=0注意此处与二维数组求解的区别i

7、f (nKnapsackcapIndexnKnapsackcapIndex-nVolumeitemIndex+nValueitemIndex)nKnapsackcapIndex = nKnapsackcapIndex-nVolumeitemIndex+nValueitemIndex; selectTableitemIndexcapIndex = 1;elsenKnapsackcapIndex = nKnapsackcapIndex;coutThe max value is: nKnapsackCAPACITYendl;cout=0;itemIndex-)if (selectTableitemI

8、ndexcapIndex)coutitemIndex+1;capIndex = capIndex - nVolumeitemIndex; coutendl;分析:在一维数组实现中将空间复杂度由O(GOODSNUM*CAPACITYf低至iJ O(CAPACITY同时进行了代码优化,同时也给出了选择物品的编号。二、完全背包问题若你能给深入理解 0-1背包问题和其深刻内涵,并真正明白一维数组求解背包问题后, 下面的问题对你来说就相当容易了。完全背包问题:有 N种物品和一个容量为 V的背包,每种物品都有无限件可用。第 i种 物品的费用是 ci,价值是wio求解将哪些物品装入背包可使这些物品的费用总和

9、不超过 背包容量,且价值总和最大。求解分析:目标是转化为 0-1背包问题。如将费用/容量为nVolumeitemIndex的物品转 化为CAPACITY /nVolumeitemIndex相同费用和价值的物品,直接用前面的三种 0-1背包问题求解。除此之外还有其它可行的求解方法吗?可以对0-1背包问题的状态方程 fiv=maxfi-1v,fi-1v-ci+wi 稍加分析可得完全背包问 题的状态方程fi v=maxfi-1v-k*ci+k*wi0=k*ci=v,因而有以下算法实现过程,并最终给出了所选 择的物品和选择该物品的数目。实现算法:#include iostream#define CAP

10、ACITY 10#define GOODSNUM 6using namespace std;void main() int num,k,max;int nVolumeGOODSNUM = 1,4,3,5,5,3;int nValueGOODSNUM = 2,8,40,60,10,3;int selectTableGOODSNUMCAPACITY+1 = 0;int nKnapsackCAPACITY+1 = 0;/most important for the first compution belowint itemIndex,capIndex;for (itemIndex=0;itemInd

11、ex=nVolumeitemIndex;capIndex-)/notice that capIndex=nVolumeitemIndex,not capIndex=0num = 0;max = nKnapsackcapIndex;for (k=1;k=k*nVolumeitemIndex&maxnKnapsackcapIndex-k*nVolumeitemIndex+k*nValueitemIndex)max = nKnapsackcapIndex-k*nVolumeitemIndex+k*nValueitemIndex;num = k;nKnapsackcapIndex = max;sele

12、ctTableitemIndexcapIndex = num; coutThe max value is: nKnapsackCAPACITYendl;coutThe selected items are: =0;itemIndex-)(if (selectTableitemIndexcapIndex)(coutitemIndex+1:selectTableitemIndexcapIndex;capIndex = capIndex - selectTableitemIndexcapIndex*nVolumeitemIndex;)coutendl;)三、多重背包问题多重背包问题:有N种物品和一个容量为V的背包。第i

温馨提示

  • 1. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
  • 2. 本站的文档不包含任何第三方提供的附件图纸等,如果需要附件,请联系上传者。文件的所有权益归上传用户所有。
  • 3. 本站RAR压缩包中若带图纸,网页内容里面会有图纸预览,若没有图纸预览就没有图纸。
  • 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
  • 5. 人人文库网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对用户上传分享的文档内容本身不做任何修改或编辑,并不能对任何下载内容负责。
  • 6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
  • 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。

评论

0/150

提交评论