动态规划-----背包类问题(0-1背包与完全背包)详解

目录

什么是背包问题?

动态规划问题的一般解决办法:

0-1背包问题:

0 - 1背包类问题  分割等和子集: 

完全背包问题: 

完全背包类问题 零钱兑换II:


什么是背包问题?

背包问题(Knapsack problem)是一种组合优化的NP完全问题。问题可以描述为:给定一组物品,每种物品都有自己的重量和价格,在限定的总重量内,我们如何选择,才能使得物品的总价格最高。问题的名称来源于如何选择最合适的物品放置于给定背包中。相似问题经常出现在商业、组合数学,计算复杂性理论、密码学和应用数学等领域中。也可以将背包问题描述为决定性问题,即在总重量不超过W的前提下,总价值是否能达到V?它是在1978年由Merkle和Hellman提出的。

动态规划问题的一般解决办法:

动态规划,无非就是利用历史记录,来避免我们的重复计算。而这些历史记录,我们得需要一些变量来保存,一般是用一维数组或者二维数组来保存。下面我们先来讲下做动态规划题很重要的三个步骤:

  • 🧐 步骤一:定义dp数组元素的含义
  • 🧐步骤二:找出数组元素之间的关系式(也就是我们所熟知的状态转移方程)
  • 🧐第三步骤:找出初始值(base case)

接下来的题目我们会按照这三个步骤来解释说明

前言:本文包含动态规划中的经典背包问题,有关背包问题的描述如下:

在动态规划中,背包问题是一个经典的优化问题,它可以分为0-1背包问题和完全背包问题两种类型。下面我们就来看看这两个问题:

0-1背包问题:

问题描述:

给你一个可装载重量为 W 的背包和 N 个物品,每个物品有重量和价值两个属性。其中第 i 个物品的重量为 wt[i],价值为 val[i]。现在让你用这个背包装物品,每个物品只能用一次,在不超过被包容量的前提下,最多能装的价值是多少?

  • 🧐 步骤一:定义dp数组元素的含义:

由于状态有两个,就是「背包的容量」和「可选择的物品」,这里我们就需要用到一个二维的dp

数组,如下为dp数组的定义:

🦉🦉🦉dp[i][w] 的定义如下:对于前 i 个物品,当前背包的容量为 w,这种情况下可以装的最大价值是 dp[i][w]

  • 🧐步骤二:找出数组元素之间的关系式(也就是我们所熟知的状态转移方程)

1.如果你没有把这第 i 个物品装入背包,那么很显然,最大价值 dp[i][w] 应该等于 dp[i-1][w],继承之前的结果(翻译一下就是不装入第i个物品,相当于对前 i - 1 个物品进行选择,对应此时的背包容量w)。即此时的状态转移方程是:dp[ i ][ w ] = dp[ i - 1 ][ w ]

2.如果你把这第 i 个物品装入了背包,此时背包剩余容量为 w - wt[ i - 1 ](wt数组下标是从0开始的, wt[ i - 1 ] 相当于第 i 个物品的重量,val 也一样)

则此时的状态转移方程是:dp[ i ][ w ] = dp[ i - 1 ][ w - wt[ i - 1] ] + val[ i - 1 ]

  • 🧐第三步骤:找出初始值(base case):

这题的base case 相对简单,当物品个数为0或则背包当前容量为0时,dp[ i ][ w ] 都等于0

按照上述的状态转移方程,我们可以填出对应dp表格(以图中的例子为例):

有了上述铺垫后,动态规划的代码就很好实现了,具体代码如下:

int knapsack(int W, int N, int[] wt, int[] val) {
    assert N == wt.length;
    // base case 已初始化,数组自动全部初始化为0
    int[][] dp = new int[N + 1][W + 1];
    for (int i = 1; i <= N; i++) {
        for (int w = 1; w <= W; w++) {
            if (w - wt[i - 1] < 0) {
                // 这种情况下只能选择不装入背包
                dp[i][w] = dp[i - 1][w];
            } else {
                // 装入或者不装入背包,择优
                dp[i][w] = Math.max(
                    dp[i - 1][w - wt[i-1]] + val[i-1], 
                    dp[i - 1][w]
                );
            }
        }
    }
    
    return dp[N][W];
}

有了上面的一定了解后,我们来看看0 - 1背包的类似题:

0 - 1背包类问题  分割等和子集: 

看一下力扣第 416 题「分割等和子集open in new window」:

题目描述:输入一个只包含正整数的非空数组 nums,请你写一个算法,判断这个数组是否可以被分割成两个子集,使得两个子集的元素和相等。对应函数签名如下:

我们可以将这个问题转化为0 - 1背包问题,具体做法:

这个问题相当于给一个可装载重量为 sum / 2 的背包和 N 个物品,每个物品的重量为 nums[i]。现在让你装物品,是否存在一种装法,能够恰好将背包装满?按照上述解题思路就是:

  • 🧐 步骤一:定义dp数组元素的含义:

dp[i][j] = x 表示,对于前 i 个物品(i 从 1 开始计数),当前背包的容量为 j 时,若 x 为 true,则说明可以恰好将背包装满,若 x 为 false,则说明不能恰好将背包装满

  • 🧐步骤二:找出数组元素之间的关系式(也就是我们所熟知的状态转移方程)

与上面类似,这里就直接给出来了:

1.不把这第 i 个物品装入背包:dp[ i ][ j ] = dp[ i - 1 ][ j ]

2.把这第i个物品装入背包:dp[ i ][ j ] = dp[ i - 1][ j - nums[ i - 1 ] ]

  • 🧐第三步骤:找出初始值(base case):

当背包容量为0时(sum / 2= 0)这时无论物体有多少个都可以满足条件,就是什么都不装嘛

ok,接下来看完整代码:

boolean canPartition(int[] nums) {
    int sum = 0;
    for (int num : nums) sum += num;
    // 和为奇数时,不可能划分成两个和相等的集合
    if (sum % 2 != 0) return false;
    int n = nums.length;
    sum = sum / 2;
    boolean[][] dp = new boolean[n + 1][sum + 1];
    // base case
    for (int i = 0; i <= n; i++)
        dp[i][0] = true;

    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= sum; j++) {
            if (j - nums[i - 1] < 0) {
                // 背包容量不足,不能装入第 i 个物品
                dp[i][j] = dp[i - 1][j];
            } else {
                // 装入或不装入背包
                dp[i][j] = dp[i - 1][j] || dp[i - 1][j - nums[i - 1]];
            }
        }
    }
    return dp[n][sum];
}

完全背包问题: 

完全背包问题与0-1背包问题类似,但不同之处在于每个物品可以选择放入背包多次(数量无限),即每个物品的选择是一个无限的选择。我们给出对应的解题方法:

  • 🧐 步骤一:定义dp数组元素的含义:

若只使用前 i 个物品(可以重复使用),当背包容量为 j 时,能装入背包的最大价值为dp[i][w] 

  • 🧐步骤二:找出数组元素之间的关系式(也就是我们所熟知的状态转移方程)

1.不将第i个物品装入背包,此时:dp[ i ][ w ] = dp[ i - 1 ][ w ]

2.将第i个物品装入背包,此时:dp[ i ][ w ] = dp[ i ][ w -wt[ i - 1] ] + val[ i - 1 ] 

  • 🧐第三步骤:找出初始值(base case):

这题与0 - 1的bas背包的base case 一致,当物品个数为0或者背包当前容量为0时,dp[ i ][ w ] 都等于0

对应的动态规划代码为:

int fullBackpack(int W, int N, int[] wt, int[] val) {
    assert N == wt.length;
    // base case 已初始化,数组自动全部初始化为0
    int[][] dp = new int[N + 1][W + 1];
    for (int i = 1; i <= N; i++) {
        for (int w = 1; w <= W; w++) {
            if (w - wt[i - 1] < 0) {
                // 这种情况下只能选择不装入背包
                dp[i][w] = dp[i - 1][w];
            } else {
                // 装入或者不装入背包,择优
                dp[i][w] = Math.max(
                    dp[i][w - wt[i-1]] + val[i-1], 
                    dp[i - 1][w]
                );
            }
        }
    }
    
    return dp[N][W];
}

完全背包类问题 零钱兑换II:

这是力扣第 518 题「零钱兑换 IIopen in new window」,题目描述:

给定不同面额的硬币 coins 和一个总金额 amount,写一个函数来计算可以凑成总金额的硬币组合数。假设每一种面额的硬币有无限个。对应函数签名如下:

我们可以把这个问题转化为完全背包问题的描述形式

有一个背包,最大容量为 amount,有一系列物品 coins,每个物品的重量为 coins[i]每个物品的数量无限。请问有多少种方法,能够把背包恰好装满?按照动态规划三步走:

  • 🧐 步骤一:定义dp数组元素的含义:

dp[i][j] 的定义如下:若只使用前 i 个物品(可以重复使用),当背包容量为 j 时,有 dp[i][j] 种方法可以装满背包。

  • 🧐步骤二:找出数组元素之间的关系式(也就是我们所熟知的状态转移方程)

1.如果你不把这第 i 个物品装入背包,也就是说你不使用 coins[i-1] 这个面值的硬币,那么凑出面额 j 的方法数 dp[i][j] 应该等于 dp[i-1][j],继承之前的结果

即状态转移方程为:dp[ i ][ j ] = dp[ i -1 ][ j ]

2.如果你把这第 i 个物品装入了背包,也就是说你使用 coins[i-1] 这个面值的硬币,那么 dp[i][j] 应该等于 dp[i][j-coins[i-1]]

即状态转移方程为:dp[ i ][ j ] = dp[ i ][ j - coins[ i - 1] ]

  • 🧐第三步骤:找出初始值(base case):

base case 为 dp[0][..] = 0, dp[..][0] = 1i = 0 代表不使用任何硬币面值,这种情况下显然无法凑出任何金额;j = 0 代表需要凑出的目标金额为 0,那么什么都不做就是唯一的一种凑法。

写出动态规划代码:

int change(int amount, int[] coins) {
    int n = coins.length;
    int[][] dp = int[n + 1][amount + 1];
    // base case
    for (int i = 0; i <= n; i++) 
        dp[i][0] = 1;

    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= amount; j++)
           //装入背包或者不装入,加起来
            if (j - coins[i-1] >= 0)
                dp[i][j] = dp[i - 1][j] 
                         + dp[i][j - coins[i-1]];
            else // < 0 只能选择不装入背包
                dp[i][j] = dp[i - 1][j];
    }
    return dp[n][amount];
}

结语: 写博客不仅仅是为了分享学习经历,同时这也有利于我巩固自己的知识点,总结该知识点,由于作者水平有限,对文章有任何问题的还请指出,接受大家的批评,让我改进。同时也希望读者们不吝啬你们的点赞+收藏+关注,你们的鼓励是我创作的最大动力!

相关推荐

  1. 动态规划09-完全背包

    2024-03-31 23:10:03       22 阅读
  2. 动态规划】【背包问题】基础背包

    2024-03-31 23:10:03       3 阅读
  3. 动态规划-背包问题-二维费用背包 & 分组背包

    2024-03-31 23:10:03       19 阅读

最近更新

  1. leetcode705-Design HashSet

    2024-03-31 23:10:03       8 阅读
  2. Unity发布webgl之后打开streamingAssets中的html文件

    2024-03-31 23:10:03       8 阅读
  3. vue3、vue2中nextTick源码解析

    2024-03-31 23:10:03       8 阅读
  4. 高级IO——React服务器简单实现

    2024-03-31 23:10:03       8 阅读
  5. 将图片数据转换为张量(Go并发处理)

    2024-03-31 23:10:03       7 阅读
  6. go第三方库go.uber.org介绍

    2024-03-31 23:10:03       8 阅读
  7. 前后端AES对称加密 前端TS 后端Go

    2024-03-31 23:10:03       10 阅读

热门阅读

  1. C语言刷题(21)

    2024-03-31 23:10:03       5 阅读
  2. 算法刷题day37

    2024-03-31 23:10:03       4 阅读
  3. 优化代码分支

    2024-03-31 23:10:03       4 阅读
  4. c语言:把百分制转化为等级制度(switch语句)

    2024-03-31 23:10:03       6 阅读
  5. 搭建语音打电话机器人需要哪些技术和资源

    2024-03-31 23:10:03       5 阅读
  6. 座次问题(蓝桥杯)

    2024-03-31 23:10:03       4 阅读
  7. css页面搭建案例

    2024-03-31 23:10:03       5 阅读
  8. 输入 wo xiang he ni jao peng you.,倒着打。

    2024-03-31 23:10:03       4 阅读