背包问题系列算法详解.doc

《背包问题系列算法详解.doc》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、背包问题系列算法详解 背包问题是一个关于最优解的经典问题。通常被讨论的最多的，最经典的背包问题是0-1背包问题(0-1KnapsackProblem)。它是一切背包问题及相关背包问题的基础。本篇博文将详细分析0-1背包问题，并给出0-1背包问题的几种解法，同时也对0-1背包问题的内涵进行延伸，丰富其外延至完全背包问题和多重背包问题，并给出背包问题的算法实现过程，希望对大家有帮助。一、0-1背包问题     有N件物品和一个容量为V的背包。第i件物品（每个物品只有一件）的费用是c[i]，价值是w[i]。求解将哪些物品装入背包

2、可使价值总和最大。（1）递归求解算法如下：#include"iostream"#defineCAPACITY10#defineGOODSNUM6usingnamespacestd;intnVol[GOODSNUM];intnValue[GOODSNUM];intknapsack(intitemIndex,intvol);voidmain(){ inti=0,j=0; while(i>nV

3、ol[i]>>nValue[i];  i++; } cout<<"Themaxvalueis:"<

4、

5、vol==0) {  return0; } elseif(vol>=nVol[itemIndex]&&knapsack(itemIndex-1,vol)

6、emIndex])  {   returnknapsack(itemIndex-1,vol-nVol[itemIndex])+nValue[itemIndex];  } else  returnknapsack(itemIndex-1,vol);}    分析：递归求解，求解过程中的绝大部分变量存在重复求解的过程，算法的效率较低，有待改进；那怎么改进呢？最有效的是用数组保存每次计算的结果，不用重复计算，于是有二维数组求解。（2）二维数组求解算法如下：#include"iostream"#defineCAPACITY10#d

7、efineGOODSNUM6usingnamespacestd;voidmain(){ inti=1,j; intv[GOODSNUM]={10,12,40,40,40,15}; intc[GOODSNUM]={1,2,3,5,2,1}; intfun[GOODSNUM+1][CAPACITY+1]; for(i=1;i<=GOODSNUM;i++) {  fun[i][0]=0; } for(i=1;i<=CAPACITY;i++) {  fun[0][i]=0; } for(i=1;i<=GOODSNUM;i++) {

8、  for(j=1;j<=CAPACITY;j++)  {   if(j

9、

10、DSNUM][CAPACITY+1]={0}; intnKnapsack[CAPACITY+1]={0};//mostimportantforthefirstcomputionbelow intitemIndex,capIndex; for(itemIndex=0;itemIndex