01背包问题,最良心的讲解了

发布时间:2018-04-13 10:00  浏览次数:52

1、动态规划(DP)

  动态规划(Dynamic
Programming,DP)与分治区别在于划分的子问题是有重叠的,解过程中对于重叠的部分只要求解一次,记录下结果,其他子问题直接使用即可,减少了重复计算过程。 
  另外,DP在求解一个问题最优解的时候,不是固定的计算合并某些子问题的解,而是根据各子问题的解的情况选择其中最优的。 
  动态规划求解具有以下的性质: 
  最优子结构性质、子问题重叠性质   
  最优子结构性质:最优解包含了其子问题的最优解,不是合并所有子问题的解,而是找最优的一条解线路,选择部分子最优解来达到最终的最优解。 
  子问题重叠性质:
先计算子问题的解,再由子问题的解去构造问题的解(由于子问题存在重叠,把子问题解记录下来为下一步使用,这样就直接可以从备忘录中读取)。其中备忘录中先记录初始状态。

<>2、求解思路

  ①、将原问题分解为子问题(子问题和原问题形式相同,且子问题解求出就会被保存); 
  ②、确定状态:01背包中一个状态就是NN个物体中第ii个是否放入体积为VV背包中; 
  ③、确定一些初始状态(边界状态)的值; 
  ④、确定状态转移方程,如何从一个或多个已知状态求出另一个未知状态的值。(递推型)

<>3、01背包问题求解思路

  ①、确认子问题和状态 
  01背包问题需要求解的就是,为了体积V的背包中物体总价值最大化,NN件物品中第ii件应该放入背包中吗?(其中每个物品最多只能放一件) 
  为此,我们定义一个二维数组,其中每个元素代表一个状态,即前ii个物体中若干个放入体积为VV背包中最大价值。数组为:f[N][V]f[N][V],其中fij
fij表示前ii件中若干个物品放入体积为jj的背包中的最大价值。 
  ②、初始状态 
  初始状态为f[0][0−V]f[0][0−V]和f[0−N][0]f[0−N][0]
都为0,前者表示前0个物品(也就是空物品)无论装入多大的包中总价值都为0,后者表示体积为0的背包啥价值的物品都装不进去。 
  ③、转移函数
if (背包体积j小于物品i的体积) f[i][j] = f[i-1][j] //背包装不下第i个物体,目前只能靠前i-1个物体装包 else
f[i][j] =max(f[i-1][j], f[i-1][j-Vi] + Wi)
  最后一句的意思就是根据“为了体积V的背包中物体总价值最大化,NN件物品中第ii件应该放入背包中吗?”转化而来的。ViVi表示第ii件物体的体积,WiWi
表示第ii件物品的价值。这样f[i-1][j]代表的就是不将这件物品放入背包,而f[i-1][j-Vi] +
Wi则是代表将第i件放入背包之后的总价值,比较两者的价值,得出最大的价值存入现在的背包之中。

<>4、程序
#include<iostream> using namespace std; int main() { int nArr[6][13] = {{0}};
int nCost[6] = {0 , 2 , 5 , 3 , 10 , 4}; //花费 int nVol[6] = {0 , 1 , 3 , 2 , 6 ,
2}; //物体体积 int bagV = 12; for( int i = 1; i< sizeof(nCost)/sizeof(int); i++) {
for( int j = 1; j<=bagV; j++) { if(j<nVol[i]) nArr[i][j] = nArr[i-1][j]; else
nArr[i][j] = max(nArr[i-1][j] , nArr[i-1][j-nVol[i]] + nCost[i]); cout
<<nArr[i][j]<<' '; } cout<<endl; } cout<<nArr[5][12]<<endl; return 0; }
*


  01背包问题其实就可以化简为涂写下面的表格,其中每个数对应数组nArr中每个元素,初始化部分为0,然后从左上角按行求解,一直求解到右下角获取最终解nArr[5][12]。 





<>
5、空间优化

  l) 空间优化,每一次f(i)(j)改变的值只与f(i-1)(x) {x:1...j}有关,f(i-1)(x)是前一次i循环保存下来的值;

  因此,可以将f缩减成一维数组,从而达到优化空间的目的,状态转移方程转换为 B(j)= max{B(j), B(j-w(i))+v(i)};


  并且,状态转移方程,每一次推导V(i)(j)是通过V(i-1)(j-w(i))来推导的,所以一维数组中j的扫描顺序应该从大到小(capacity到0),否者前一次循环保存下来的值将会被修改,从而造成错误。

 



标签

归档

阅读排行

支付宝搜索“559315787”,天天领红包