算法分析设计——0-1背包问题

文章结构概览

• 1 三种背包问题详解

  • 2 最值问题

  • • 1.1 0-1背包问题
    • 1.2 零钱兑换
    • 1.3 一和零
    • 1.4 最后一块石头的重量

  • 3. 恰好背包容量问题

  • 4. 排列组合问题

  • • 4.1 目标和
    • 4.2 组合总和Ⅳ

在完成对数据结构的基础回顾之后，算法方面的学习随即展开。本篇文章将融合复习课程内容与LeetCode平台上的题目，专门针对机考环境下的算法复习进行整理。关于动态规划中的背包问题，通常可以划分为以下三类典型题型：

• 最值问题 ：在给定物品集合与限定容量的前提下，目标是计算所能获得的最大价值或最大体积。
  ①0-1背包问题
  ②完全背包问题。

• 恰好取到背包容量的问题
  ①0-1背包问题 + 恰好填满背包容量的情形。

• 组合类问题
  ①需考虑排列顺序的组合类型。
  ②0-1背包相关的组合类型。

1 三种背包问题详解

三种背包问题均以0-1背包问题为理论基础，因此接下来将从0-1背包问题入手，依次阐述各类问题的求解方法。
（1）0-1背包问题 ：

• 最大价值
  $dp[i][j]=\begin{cases} dp[