博客
关于我
强烈建议你试试无所不能的chatGPT,快点击我
01背包问题
阅读量:4050 次
发布时间:2019-05-25

本文共 3245 字,大约阅读时间需要 10 分钟。

【转】http://blog.csdn.net/mu399/article/details/7722810

01背包问题,是用来介绍动态规划最经典的例子,网上关于01背包问题的讲解也很多,我写这篇文章力争做到用最简单的方式,最少的公式把01背包问题讲解透彻。

01背包的状态转换方程 f[i,j] = Max{ f[i-1,j-Wi]+Pi( j >= Wi ),  f[i-1,j] }

f[i,j]表示在前i件物品中选择若干件放在承重为 j 的背包中,可以取得的最大价值。
Pi表示第i件物品的价值。
决策:为了背包中物品总价值最大化,第 i件物品应该放入背包中吗 ?

题目描述:

有编号分别为a,b,c,d,e的五件物品,它们的重量分别是2,2,6,5,4,它们的价值分别是6,3,5,4,6,现在给你个承重为10的背包,如何让背包里装入的物品具有最大的价值总和?

name weight value 1 2 3 4 5 6 7 8 9 10
a 2 6 0 6 6 9 9 12 12 15 15 15
b 2 3 0 3 3 6 6 9 9 9 10 11
c 6 5 0 0 0 6 6 6 6 6 10 11
d 5 4 0 0 0 6 6 6 6 6 10 10
e 4 6 0 0 0 6 6 6 6 6 6 6

只要你能通过找规律手工填写出上面这张表就算理解了01背包的动态规划算法。

首先要明确这张表是至底向上,从左到右生成的。

为了叙述方便,用e2单元格表示e行2列的单元格,这个单元格的意义是用来表示只有物品e时,有个承重为2的背包,那么这个背包的最大价值是0,因为e物品的重量是4,背包装不了。

对于d2单元格,表示只有物品e,d时,承重为2的背包,所能装入的最大价值,仍然是0,因为物品e,d都不是这个背包能装的。

同理,c2=0,b2=3,a2=6。

对于承重为8的背包,a8=15,是怎么得出的呢?

根据01背包的状态转换方程,需要考察两个值,

一个是f[i-1,j],对于这个例子来说就是b8的值9,另一个是f[i-1,j-Wi]+Pi;

在这里,

 f[i-1,j]表示我有一个承重为8的背包,当只有物品b,c,d,e四件可选时,这个背包能装入的最大价值

f[i-1,j-Wi]表示我有一个承重为6的背包(等于当前背包承重减去物品a的重量),当只有物品b,c,d,e四件可选时,这个背包能装入的最大价值

f[i-1,j-Wi]就是指单元格b6,值为9,Pi指的是a物品的价值,即6

由于f[i-1,j-Wi]+Pi = 9 + 6 = 15 大于f[i-1,j] = 9,所以物品a应该放入承重为8的背包

------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------

01背包问题

问题:有N件物品和一个容量为V的背包。第i件物品的费用是c[i],价值是w[i]。求解将哪些物品装入背包可使价值总和最大。

分析:

这是最基础的背包问题,特点是:每种物品仅有一件,可以选择放或不放。

用子问题定义状态:即f[i][v]表示前i件物品恰放入一个容量为v的背包可以获得的最大价值。则其状态转移方程便是:

f[i][v]=max{f[i-1][v],f[i-1][v-c[i]]+w[i]}

这个方程非常重要,基本上所有跟背包相关的问题的方程都是由它衍生出来的。所以有必要将它详细解释一下:“将前i件物品放入容量为v的背包中”这个子问题,若只考虑第i件物品的策略(放或不放),那么就可以转化为一个只牵扯前i-1件物品的问题。如果不放第i件物品,那么问题就转化为“前i-1件物 品放入容量为v的背包中”,价值为f[i-1][v];如果放第i件物品,那么问题就转化为“前i-1件物品放入剩下的容量为v-c[i]的背包中”,此时能获得的最大价值就是f[i-1][v-c[i]]再加上通过放入第i件物品获得的价值w[i]。

优化:

以上方法的时间和空间复杂度均为O(VN),其中时间复杂度应该已经不能再优化了,但空间复杂度却可以优化到O。

先考虑上面讲的基本思路如何实现,肯定是有一个主循环i=1..N,每次算出来二维数组f[i][0..V]的所有值。那么,如果只用一个数组 f[0..V],能不能保证第i次循环结束后f[v]中表示的就是我们定义的状态f[i][v]呢?f[i][v]是由f[i-1][v]和f[i-1] [v-c[i]]两个子问题递推而来,能否保证在推f[i][v]时(也即在第i次主循环中推f[v]时)能够得到f[i-1][v]和f[i-1] [v-c[i]]的值呢?事实上,这要求在每次主循环中我们以v=V..0的顺序推f[v],这样才能保证推f[v]时f[v-c[i]]保存的是状态 f[i-1][v-c[i]]的值。伪代码如下:

for i=1..N
    for v=V..0
        f[v]=max{f[v],f[v-c[i]]+w[i]};

/***************01背包问题******************/#include 
using namespace std;#define INF -65536const int V=1000;//定义体积的最大值;const int T=5;//定义商品的数目;int f[V+1];//#define EMPTYint w[T]={6,8,3,9,2};//商品的价值;int c[T]={400,600,500,600,900};//商品的体积;int package(){#ifdef EMPTY//可以不装满 for(int i=0;i<=V;i++)//条件编译,表示可以不存储满 { f[i]=0; }#else//必须装满 f[0]=0; for(int i=1;i<=V;i++)//条件编译,表示必须存储满 { f[i]=INF; }#endif // EMPTY for(int i=0;i
=c[i];v--) { f[v]=max(f[v],f[v-c[i]]+w[i]); } } return f[V];}int main(){ int temp; temp=package(); cout<
<
ps:

我们看到的求最优解的背包问题题目中,事实上有两种不太相同的问法。有的题目要求“恰好装满背包”时的最优解,有的题目则并没有要求必须把背包装满。一种区别这两种问法的实现方法是在初始化的时候有所不同。

如果是第一种问法,要求恰好装满背包,那么在初始化时除了f[0]为0其它f[1..V]均设为-∞,这样就可以保证最终得到的f[N]是一种恰好装满背包的最优解。

如果并没有要求必须把背包装满,而是只希望价格尽量大,初始化时应该将f[0..V]全部设为0。

为什么呢?可以这样理解:初始化的f数组事实上就是在没有任何物品可以放入背包时的合法状态。如果要求背包恰好装满,那么此时只有容量为0的背包可能被价值为0的nothing“恰好装满”,其它容量的背包均没有合法的解,属于未定义的状态,它们的值就都应该是-∞了。如果背包并非必须被装满,那么 任何容量的背包都有一个合法解“什么都不装”,这个解的价值为0,所以初始时状态的值也就全部为0了。

你可能感兴趣的文章
区块链技术让Yotta企业云盘为行政事业服务助力
查看>>
Yotta企业云盘更好的为媒体广告业服务
查看>>
Yotta企业云盘助力科技行业创高峰
查看>>
Yotta企业云盘更好地为教育行业服务
查看>>
Yotta企业云盘怎么帮助到能源化工行业
查看>>
企业云盘如何助力商业新发展
查看>>
医疗行业运用企业云盘可以带来什么样的提升
查看>>
媒体广告业如何将内容资产进行高效地综合管理与利用
查看>>
能源化工要怎么管控核心数据
查看>>
媒体广告业如何运用云盘提升效率
查看>>
企业如何运用企业云盘进行数字化转型-实现新发展
查看>>
司法如何运用电子智能化加快现代化建设
查看>>
iSecret&nbsp;1.1&nbsp;正在审核中
查看>>
IOS开发的开源库
查看>>
IOS开发的开源库
查看>>
Jenkins - sonarqube 代码审查
查看>>
Jenkins + Docker + SpringCloud 微服务持续集成(一)
查看>>
Jenkins + Docker + SpringCloud 微服务持续集成 - 单机部署(二)
查看>>
Jenkins + Docker + SpringCloud 微服务持续集成 - 高可用集群部署(三)
查看>>
Golang struct 指针引用用法(声明入门篇)
查看>>