背包问题系列算法详解

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