动态规划解0-1背包问题

动态规划解0-1背包问题是一个十分典型案例,我从网上查询好多相关资料,但是大部分都深奥难懂,并不适合初学算法的小白,其中涉及的递推关系式、填表,以及最后的二维表简化为一维表的优化过程,好多都是一笔带过,所以,今天就尽我所能,来叙述一下对于0-1背包问题使用动态规划来求解。 要解决0-1背包问题,首先咱们要解决的是什么是动态规划。

动态规划

先说一说什么是动态规划。 动态规划算法与分治算法类似,其基本思想也是将待求解问题分解成若干个子问题,先求解子问题,然后从这些子问题的解得到原问题的解。 这里又涉及到分治算法,那就简单概述一下分治算法。分治算法简而言之就是将一个大问题分成若干个小问题,通过求解小问题的最优解,进而推出所求解问题的最优解。 这么乍一看,可能会觉得分治算法与动态规划相类似,实际上,他们有一个最本质的区别,那就是子问题的类型不同。 分治算法的子问题是相互独立的,子问题与子问题之间并没有什么关联。而动态规划的子问题就有意思了,他们是重叠的子问题。这么单纯的用文字来描述可能有点难以理解,我们借用一张图来声明

从这张图我们可以看出,当我们对所求问题进行子问题划分时,会产生很对相同的子问题,这些子问题在计算机中我们已经求得结果一次,再另一个子问题中,我们如果再让计算机求解相同的子问题,显然有点不太地道。 而这种一遍一遍求解相同子问题,如果当问题为n时,显然我们付出的时间是相当大的。 为了解决这个问题,动态规划表示,可以用一张数组来记录下我们之前已经求解的子问题结果,当我们再次调用时,只需先从数组中查询是否有所求子问题的结果,如果有,皆大欢喜,直接把答案调出来使用,如果没有,就将该问题的解存储进去,为了下一次查询提供结果。 这么看来,我们就是在用空间换时间,实际上就是如此。 简单来说,求解动态规划的核心是穷举,因为要求最值,所以要把所有可行的答案穷举出来,然后在其中找最值。而在我们穷举的过程中,我们会把碰到的解相同的子问题用一个数组记录下来。

通过上述所言,我们讲清楚了什么是动态规划。

进而,我们可以总结出,要想使用动态规划,我们的问题必不可少两个基本要素是:

  • 最优子结构性质
  • 重叠子问题

当我们的问题具备这两个基本要素后,我们便可以考虑使用动态规划来求解问题。

0-1背包问题

实现我们来了解一下什么是0-1背包问题。 在学习到动态规划算法之前,相想必我们也接触过贪心算法。 而在贪心算法中,我们也肯定接触过一个经典案例,那就是用贪心算法求解背包问题。 没接触过也没有关系,我们只是用贪心算法解背包问题来类比一下,所以我们只需要了解用贪心算法解决背包问题的大体思路用贪心算法解背包问题的基本步骤: 首先计算每种物品单位重量的价值v[i]/w[i],然后,依贪心选择策略,将尽可能多的单位重量价值最高的物品装入背包。若将这种物品全部装入背包后,背包内的物品总重量未超过C,则选择单位重量价值次高的物品并尽可能多地装入背包。依此策略一直地进行下去,直到背包装满为止。 贪心算法解决背包问题,无疑是一种十分方便的方法,但是在0-1背包问题中,我们增加了一条限制,就是我们并不能取得平均价值,比如说一个苹果重5斤,价值是5,平均价值是1,但是当背包还剩下2斤的容量时,我们不可能装下2/5个苹果,所以,就衍生出来了我们的0-1背包问题:

有n个物品,它们有各自的体积和价值,现有给定容量的背包,如何让背包里装入的物品具有最大的价值总和?

那么我们就来解决一下这个不可分割的背包问题。 解题之前先要梳理思路,该题的思路是一般动态规划的解题思路,就是将大问题化成子问题,然后动态填表的过程。而该题的核心是如何动态填表。

背包问题抽象化

把背包问题抽象化,Vi表示第 i 个物品的价值,Wj表示第 i 个物品的体积(重量),设dp[i][j]为背包为j时前i个物品的总价值。 也就是说,dp[1]2]的值就是我们背包为2时,装入第一个物品时的总价值。 在这里不得不说一句,我们的i,j最好是从1开始取值,因为在我们的递推方程中,我们可以看到[j-1],[i-1],这时如果我们从0开始取值,我们就会发现出现数组越界的现象。 在这里可能会很难看出我们的状态转移方程,我们不妨打表来推出我们的dp数组。(dp就是我们的递推数组,i表示物品,j表示背包容量,dp值为总价值) 这样我们就可以通过打表: 首先初始化边界,dp(0,j)=dp(i,0)=0由于我们会用到dp[i-1][j-1],如果我们的i,j从0开始迭代,就容易出现越界,所以这里我们通常迭代从1开始。

W0-W4是物品编号,M0-M8是背包的容量,表中绿色区域表示dp值,即该背包容量下,前n个物品可装入的最大价值。

通过打表,当我们打到M3,W2时,我们发现一个问题,就是在dp[2][3],我们有两种选择:即容量为3,我们可以选W2,也可以选择W1,因为dp为可装入物品的价值的最大值,这是我们需要比较W1与W2的价值,选择价值大的一个,如果价值W2>W1,则dp[2][3]=W2的价值,否则dp的值是W1的价值,在此时,我们可以看到W2>W1,所以我们填入W2的价值。

如此继续打表

我们可以看到,当我们的背包容量不足以装下新的物品时,实际上它的值是相同背包容量下,前n-1个物品的最大价值。即dp[i][j]=dp[i-1][j]; 当可以装下新加入的物品时,得到新的dp递推公式。 但是在得到递推公式之前我们需要知道,我们的dp[i][j]值是最大值,也就是说。我们需要比较,即max(dp[i][j-wi]+新物品的价值,dp[i-1][j]),取最值。 这样,通过打表的方式,我们得到了递推公式。 做到这里,我们就已经将0-1背包问题解决。 接下来我们来实现代码

int W[30],C[30];//w是物品重量,C是物品价值,测试数量不能超过30
int main()
{
    int,m,n;//m为背包容量,n为物品数量
    scanf("%d%d",&m&n);
    for(int i=0;i<n;i++){
        scanf("%d%d",&w[i]&c[i]);
    }
    for(int i = 1;i<=n;i++){
        for(int j =1;j<=m;j++){
            if(j>w[i]){
                dp[i][j]=dp[i-1][j];
            }else{
                dp[i][j]=max(dp[i-1][j],dp[i-1][j-w[i]]+c[i]);
            }
        }
    }
}

代码优化

通过代码,我们实现了动态规划解决0-1背包问题。但是我们不难发现,这样通过一个二维表十分的浪费空间,我们可不可以优化代码呢。

我们来看递推公式,不难发现,实际上, dp二维表可以化为一维表。 j > w[i]时,dp[i]=dp[i-1] j < w[i]时,dp[j] = dp[j - w[i]] + v[i];

#include<stdio.h>
int main() {
    //动态规划解0-1背包问题
    //递推公式:dp[j]=dp[j-w[i]]+v[i]
    int m, n;//m为背包容量,n为物品数量,n小于20;
    int w[20], v[20],dp[20];//w[i]为第i件物品的重量,v[i]是第i件物品的价值,dp[]为递推数组
    scanf("%d %d", &m, &n); //m为背包容量,n为物品数量,n小于20;
    for (int j = 0; j<= m; j++) {
        dp[j] = 0; //dp置零
    }
    for (int i = 1; i <= n; i++) {
        scanf("%d %d", &w[i], &v[i]);
    }
    for (int i = 1; i <= n; i++) {
        for (int j = m; j >= 0; j--) {
            if (j >= w[i]) {
            dp[j] = dp[j - w[i]] + v[i];
            }
        }
    }
    printf("%d", dp[m]);
    return 0;
}

由此我们用动态规划将0-1背包问题讲了个大概。

作者:|喝茶谢谢|,原文链接: https://www.cnblogs.com/myn-drink-tea/p/16304977.html

文章推荐

选择排序的简单理解

『忘了再学』Shell基础 — 26、cut列提取命令

python常用标准库(os系统模块、shutil文件操作模块)

jenkins中maven的安装及配置,如何在jenkins中创建ma

新入职,如何快速熟悉一个项目的代码

Spark: 单词计数(Word Count)的MapReduce实现(Java/Python)

Hadoop: 单词计数(Word Count)的MapReduce实现

CSAPP 之 ShellLab 详解

推荐一款新框架PyScript:在 HTML 嵌入 Python 代码!

DM 是如何处理 DML 的丨TiDB 工具分享

聊聊如何验证线上的版本是符合预期的版本

sqlx操作MySQL实战及其原理