【算法】——动态规划之0-1背包问题

布满荆棘的人生 2022-07-16 10:15 191阅读 0赞

借着软考的机会，好好的研究了一下关于算法部分的内容，其中动态规划也是非常实用的算法，之前觉得看算法是非常难理解，后来用了一张图竟然神奇的看懂了，下面小编画给大家看！

# 动态规划法基本思想 #

将待求解的问题分解成若干个子问题，先求解子问题，然后从浙西子问题的解得得到原问题的解。但是动态规划的到子问题的解不是孤立的，保存在已解决的子问题的答案，在需要时找出以求的答案，避免大量的重复计算。为了达到目的用一张二维表来记录所有已解决的子问题的答案。

## 解决步骤 ##

1）、找出最优解的性质，并刻画其结构特征

2）、递归地定义最优解的值

3）、以自底向上方法计算出最优值

4）、根据计算最优值时得到的信息，构造一个最优解

## 为什么自底向上计算？ ##

动态规划法思想提出，用一张表记录已解决问题的答案，当有需要的时候可以借助之前解决过的子问题进行求解。而动态规划经常会用到递归的方式求解。

## 什么样的问题使用动态规划法？ ##

1）、最优子结构

2）、重叠子结构

## 0-1背包问题递归定义求最优解 ##

i表示放入的第i物品，w表示背包可容纳的质量

C\[i,w\]表示包中放有i件物品，可容纳质量为w时的价值

![Center][]

1、先解释为什么C\[i,w\]会等于0？

当背包中没有物品可以放入的时候，此时i为0，背包的价值为0，当背包中可容纳的物品质量为0时，此时w=0，背包的价值同样为0

2、什么时候C\[i,w\]= C\[i-1,w\]？

当要放入第i件物品的时候，可是i物品的质量wi大于当前背包所能装下的总质量w，所以i不能放入，此时当想把第i件放入背包的价值等于放入i-1的价值

3、当上述两种情况都不存在时候，0-1背包就是在比较第i件物品放入还不放入的时候价值最大？

当i放入的时候

此时背包相当于在放入i-1件物品，重量为w-wi的背包中放入了一件价值为Vi物品，则C\[i,w\]=C\[i-1,w-wi\]+Vi;

当i不放入的时候

此时背包相当于放入i-1件物品，在重量为w的背包中，则此时价值C\[i-1,w\]。

# 题目描述 #

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

首先用一张表来表示这个动态规划的过程，切记这种表是自底向上，而且是从左到右生成的。

![Center 1][]

举个例子

E行4列，用坐标表示c（1,4），具体的含义是只有E物品时，有个承重为4的背包，此时背包的价值为6。

那么c（5,9）此时背包价值为15，又是怎样计算的呢？

根据前面的知识讲解，在求得15之前判断A物品到底该不该放入？

当A不放入的时候

其实是把E，D，C，B放入承重为9的背包中，求最优结构，也就是C\[i-1,w\]=C\[4,9\],查表得此时背包价值为10

当A放入的时候

其实是把E、D、C、B放入承重为7的背包中，然后加上A物品的价值，就是C\[i-1,w-wi\]+VA=C\[4,7\]+VA=15

根据公式得Max c\[i-1,w-wi\]+vi, c\[i-1,w\]  此时最大值为15

# 总结 #

小编感觉动态规划法的学习主要是搞懂算法的含义，知道求得最优解的三个方法非常重要，它能帮助我们更好的了解算法的思想。动态规划法就是先把问题拆解，然后从基础做起，学会站在巨人的肩膀上，就是尝试使用之前的劳动成果，从而到达效率提高的目的。

**如有理解偏颇之处，还请各位大神斧正，不胜感激！**

[Center]: /images/20220716/74961b06939d4255bd8ce1d735f07eb4.png
[Center 1]: /images/20220716/08b2d8e54264480fab4992f315ba764a.png

发表评论取消回复

表情：

评论列表（有 0 条评论，191人围观）

还没有评论，来说两句吧...

相关阅读

相关【动态规划】01背包问题

文章目录动态规划（背包问题） 1. 01背包 2. 分割等和子集 3. 目标和 4. 最后一块石头的重量 |

以你之姓@/ 2024年03月03日 08:06/ 0 赞/ 72 阅读

相关动态规划之01背包

\1038 : 01背包时间限制: 20000ms 单点时限: 1000ms 内存限制: 256MB <table></table> 描述且说上一周的故

叁歲伎倆/ 2022年08月19日 01:45/ 0 赞/ 219 阅读

相关动态规划-01背包问题

原文出处:http://www.cnblogs.com/SDJL/archive/2008/08/22/1274312.html [点击下载01背包测试数据.rar][01_

短命女/ 2022年06月11日 02:36/ 0 赞/ 258 阅读

相关动态规划之01背包问题

01背包问题，是用来介绍动态规划算法最经典的例子。 01背包的状态转换方程 f\[i,j\] = Max\{ f\[i-1,j-Wi\]+Pi( j >= Wi ), f\[

我会带着你远行/ 2022年06月10日 12:45/ 0 赞/ 269 阅读

相关动态规划之01背包问题

动态规划是在已经找到最优的子集的前提下得到最优解。基础01背包问题：有N件物品和一个容量为V的背包。第i件物品的重量是w\[i\]，价值是v\[i\]。求解将哪些物品

朱雀/ 2022年06月09日 01:28/ 0 赞/ 279 阅读

相关总结——01背包问题（动态规划算法）

0-1 背包问题：给定 n 种物品和一个容量为 C 的背包，物品 i 的重量是 wi，其价值为 vi 。问：应该如何选择装入背包的物品，使得装入背包中的物品的总价值最大？

曾经终败给现在/ 2022年05月30日 01:21/ 0 赞/ 270 阅读

相关动态规划01背包问题

做个笔记记录一下： > 给定n种物品和一个容量为 C的背包，物品i的重量是w，其价值为v 。 > > 问：应该如何选择装入背包的物品，使得装入背包中的物品的总价值最大？

女爷i/ 2022年05月30日 00:47/ 0 赞/ 500 阅读

相关动态规划 -- 01 背包问题

问题描述：假设现有容量m kg的背包，另外有n个物品，重量分别为w\[1\] w\[2\] ... w\[i\] （kg）,价值分别为p\[1\] p\[2\] ... p

浅浅的花香味﹌/ 2022年02月26日 00:10/ 0 赞/ 409 阅读

相关 [转载]01背包问题（动态规划算法）

0-1 背包问题：给定 n 种物品和一个容量为 C 的背包，物品 i 的重量是 wi，其价值为 vi 。问：应该如何选择装入背包的物品，使得装入背包中的物品的总价值最大？

Myth丶恋晨/ 2021年11月09日 07:32/ 0 赞/ 395 阅读

相关动态规划-01背包问题

文章目录题目背景题目分析状态转移方程对应价值表具体代码题目背景 > 现在有四个物品

我不是女神ヾ/ 2021年09月07日 06:03/ 0 赞/ 520 阅读