背包问题系列算法详解

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

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

2、包可使价值总和鉍人。(1)递归求解算法如卜、#includeniostream”#defineCAPACITY10#defineGOODSNUM6usingnamespacestd;intnVol[GOODSNUM];intnValue[GOODSNUM];intknapsack(intitemlndex，intvol);voidmain(){inti=0,j=0;while(i

3、»nValue[i];i++;}cout«?.Themaxvalueis:"«knapsack(GOODSNUM,CAPACITY)«endl;intknapsack(intitemlndex’intvol)if(itemlndex==0

4、

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

6、nknapsack(itemlndex-1,vol-nVol[itemlndex])+nValue[itemlndex];}elsereturnknapsack(itemlndex-1,vol);}分析：递归求解，求解过程屮的绝人部分变量存在重复求解的过程，算法的效率较低，有待改进；那怎么改进呢？最有效的是用数组保存每次计算的结果，不用重a计算，于是冇二维数组求解。(1)二维数组求解算法如下：include"iostream"#defineCAPACITY10#defineGOODSNUM6usingnamesp

7、acestd;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][O]=0;}for(i=1;i<=CAPACITY;i++){fun[0][i]=0;}for(i=1;i<=GOODSNUM;i++){for(j=1;j<=CAPACITY;j++){if(j

8、{fun[i][j]=fun[i-1][j]；}elseif(fun[i-1]0]

9、•#include"iostream"#defineCAPACITY10#defineGOODSNUM6usingnamespacestd;voidmain(){intnVolume[GOODSNUM]={1,2,3,5,2,1};intnValuefGOODSNUM]={10,12,40,40,40,15};intselectTable[GOODSNUM][CAPACITY+1]={0};intnKnapsack[CAPACITY+1]={0};//mostimportantforthefirstcomputi

10、onbelowintitemlndex,caplndex;for(itemlndex=0;itemlndex=nVolume[itemlndex];caplndex-)//noticethatcaplndex>=nVolume[itemlndex],notcapln