背包问题系列算法详解
- 格式:docx
- 大小:17.76 KB
- 文档页数:5
背包问题系列算法详解
背包问题是一个关于最优解的经典问题。通常被讨论的最多的,最经典的背包问题是0-1背包问题(0-1 Knapsack Problem)。它是一切背包问题及相关背包问题的基础。本篇博文将详细分析0-1背包问题,并给出0-1背包问题的几种解法,同时也对0-1背包问题的内涵进行延伸,丰富其外延至完全背包问题和多重背包问题,并给出背包问题的算法实现过程,希望对大家有帮助。
一、0-1背包问题
有N件物品和一个容量为V的背包。第i件物品(每个物品只有一件)的费用是c[i],价值是w[i]。求解将哪些物品装入背包可使价值总和最大。
(1)递归求解
算法如下:
#include "iostream"
#define CAPACITY 10
#define GOODSNUM 6
using namespace std;
int nVol[GOODSNUM];
int nValue[GOODSNUM];
int knapsack(int itemIndex,int vol);
void main()
{
int i=0,j=0;
while(i { cout<<"input the "< cin>>nVol[i]>>nValue[i]; i++; } cout<<"The max value is: "< } int knapsack(int itemIndex,int vol) { if (itemIndex==0||vol==0) { return 0; } else if (vol>=nVol[itemIndex] && knapsack(itemIndex-1,vol) { return knapsack(itemIndex-1,vol-nVol[itemIndex])+nValue[itemIndex]; } else return knapsack(itemIndex-1,vol); 分析:递归求解,求解过程中的绝大部分变量存在重复求解的过程,算法的效率较低,有待改进;那怎么改进呢?最有效的是用数组保存每次计算的结果,不用重复计算,于是有二维数组求解。 (2)二维数组求解 算法如下: #include "iostream" #define CAPACITY 10 #define GOODSNUM 6 using namespace std; void main() { int i=1,j; int v[GOODSNUM] = {10,12,40,40,40,15}; int c[GOODSNUM] = {1,2,3,5,2,1}; int fun[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++) { for (j=1;j<=CAPACITY;j++) { if (j { fun[i][j] = fun[i-1][j]; } else if (fun[i-1][j] { fun[i][j] = fun[i-1][j-c[i-1]] + v[i-1]; } else fun[i][j] = fun[i-1][j]; } } cout<<"The max value is: "< } 分析:二维数组求解方法相比递归求解要优越很多,但是其空间复杂度依然较高,还有继续改进的余地吗?一维数组是否可行呢?答案是肯定的 (3)一维数组求解 算法分析: #include "iostream" #define CAPACITY 10 #define GOODSNUM 6 using namespace std; void main() { int nVolume[GOODSNUM] = {1,2,3,5,2,1}; int nValue[GOODSNUM] = {10,12,40,40,40,15}; int selectTable[GOODSNUM][CAPACITY+1] = {0}; int nKnapsack[CAPACITY+1] = {0};//most important for the first compution below int itemIndex,capIndex; for (itemIndex=0;itemIndex { for (capIndex=CAPACITY;capIndex>=nVolume[itemIndex];capIndex--)//notice that capIndex>=nVolume[itemIndex],not capIndex>=0 注意此处与二维数组求解的区别 { if (nKnapsack[capIndex] { nKnapsack[capIndex] = nKnapsack[capIndex-nVolume[itemIndex]]+nValue[itemIndex]; selectTable[itemIndex][capIndex] = 1; } else nKnapsack[capIndex] = nKnapsack[capIndex]; } } cout<<"The max value is: "< cout<<"The selected items are: "; for (itemIndex = GOODSNUM-1,capIndex = CAPACITY;itemIndex>=0;itemIndex--) { if (selectTable[itemIndex][capIndex]) { cout< capIndex = capIndex - nVolume[itemIndex]; } } cout< } 分析:在一维数组实现中将空间复杂度由O(GOODSNUM*CAPACITY)降低到O(CAPACITY)并同时进行了代码优化,同时也给出了选择物品的编号。 二、完全背包问题 若你能给深入理解0-1背包问题和其深刻内涵,并真正明白一维数组求解背包问题后,下面的问题对你来说就相当容易了。