毛豆

用户名：liuyt

访问量：16848

签　名：

等　　级
排　　名	1025
经　　验	3310
参赛次数	3
文章发表	34
年　　龄	22
在职情况	学生
学　　校	燕山大学
专　　业	计算机

　　自我简介：

TA的其他文章

肺炎大作战-题解(C++代码)
浏览：186

你可能喜欢

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

　　作者: 毛豆　　　　发表时间：2019-06-27 22:04:23 浏览：1135　|　评论：0　

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

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

3、01背包问题求解思路
　　①、确认子问题和状态 
　　01背包问题需要求解的就是，为了体积V的背包中物体总价值最大化，件物品中第件应该放入背包中吗？（其中每个物品最多只能放一件） 
　　为此，我们定义一个二维数组，其中每个元素代表一个状态，即前个物体中若干个放入体积为背包中最大价值。数组为：，其中表示前件中若干个物品放入体积为的背包中的最大价值。 
　　②、初始状态 
　　初始状态为和都为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的背包中物体总价值最大化，件物品中第件应该放入背包中吗？”转化而来的。表示第件物体的体积，表示第件物品的价值。这样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]。 
![](/image_editor_upload/20190627100404_93171.jpg)
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)，否者前一次循环保存下来的值将会被修改，从而造成错误。
![](/image_editor_upload/20190627100133_29901.png)
![](/image_editor_upload/20190627100254_11035.png)

0.0分

2 人评分

看不懂代码解释一下代码? 或者生成一段代码？试试AI编程助手吧

毛豆

TA的其他文章

你可能喜欢

C语言程序设计教程（第三版）课后习题5.8 （C语言代码）

C语言程序设计教程（第三版）课后习题6.1 （C语言代码）

简单的a+b （C语言代码）

C语言程序设计教程（第三版）课后习题6.7 （C语言代码）

【绝对值排序】（C语言代码）

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

评论区

精彩推荐

C语言程序设计教程（第三版）课后习题6.8 （C++代码）

C语言程序设计教程（第三版）课后习题11.11 （C语言代码）

C语言程序设计教程（第三版）课后习题10.5 （C语言代码）

简单的a+b （C语言代码）

C语言训练-计算1~N之间所有奇数之和（C语言代码）

C语言程序设计教程（第三版）课后习题7.2 （C语言代码）

C语言程序设计教程（第三版）课后习题1.5 （C语言代码）

字符逆序（C语言代码）

C语言程序设计教程（第三版）课后习题11.3 （C语言代码）

C二级辅导-同因查找（C语言代码）

毛豆

TA的其他文章

你可能喜欢

C语言程序设计教程（第三版）课后习题5.8 （C语言代码）

C语言程序设计教程（第三版）课后习题6.1 （C语言代码）

简单的a+b （C语言代码）

C语言程序设计教程（第三版）课后习题6.7 （C语言代码）

【绝对值排序】 （C语言代码）

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

评论区

精彩推荐

C语言程序设计教程（第三版）课后习题6.8 （C++代码）

C语言程序设计教程（第三版）课后习题11.11 （C语言代码）

C语言程序设计教程（第三版）课后习题10.5 （C语言代码）

简单的a+b （C语言代码）

C语言训练-计算1~N之间所有奇数之和 （C语言代码）

C语言程序设计教程（第三版）课后习题7.2 （C语言代码）

C语言程序设计教程（第三版）课后习题1.5 （C语言代码）

字符逆序 （C语言代码）

C语言程序设计教程（第三版）课后习题11.3 （C语言代码）

C二级辅导-同因查找 （C语言代码）

【绝对值排序】（C语言代码）

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

　　评论区

C语言训练-计算1~N之间所有奇数之和（C语言代码）

字符逆序（C语言代码）

C二级辅导-同因查找（C语言代码）