01背包问题动态规划算法代码

在这里插入图片描述

01背包问题是一类经典的动态规划问题，通常描述为：有一个固定容量的背包，以及一组物品，每件物品都有重量和价值，目标是找到在背包容量范围内，使得背包中的物品总价值最大的组合。

具体来说，问题的输入包括：

一个固定容量的背包（通常表示为一个整数）。
一组物品，每个物品有两个属性：重量（通常表示为一个整数）和价值（通常表示为一个整数）。
求解的目标是找到一种放置物品的方式，使得放入背包的物品的总重量不超过背包容量，并且总价值最大。

这个问题的特点是，对于每件物品，你只能选择将其放入背包一次（0-1，因此称为“01背包”），或者不放入背包。不能将物品切割成更小的部分放入背包，要么整个物品放入背包，要么不放入。

动态规划解法：

定义状态： 通常使用二维数组表示在前个物品中，背包容量为时的最大总价值。
状态转移方程： 考虑第个物品，可以选择放入背包或者不放入。如果选择放入，那么总价值为，即前个物品的总价值加上当前物品的价值。如果选择不放入，那么总价值为，即前个物品的总价值。因此，状态转移方程为：
其中，表示不放入第个物品，表示放入第个物品。
初始条件： 当时，表示前0个物品，总价值为0；当时，表示背包容量为0，总价值也为0。
遍历顺序： 外层循环遍历物品，内层循环遍历背包容量。
返回结果： 最终结果存储在中，其中为物品数量，为背包容量。

例子：

假设有如下物品：

背包容量为，我们要求解在这个条件下的最大总价值。

按照上述动态规划解法，构建状态转移表如下：

因此，最终结果为，表示在背包容量为8的情况下，最大总价值为11。这意味着最优解是选择物品2和物品4放入背包。

题目链接：https://www.nowcoder.com/practice/fd55637d3f24484e96dad9e992d3f62e?tpId=230&tqId=&ru=/exam/oj&qru=/ta/dynamic-programming/question-ranking&sourceUrl=%2Fexam%2Foj%3Fpage%3D1%26tab%3D%25E7%25AE%2597%25E6%25B3%2595%25E7%25AF%2587%26topicId%3D196

你有一个背包，最多能容纳的体积是V。

现在有n个物品，第i个物品的体积为vi,价值为wi。

（1）求这个背包至多能装多大价值的物品？

（2）若背包恰好装满，求至多能装多大价值的物品？

输入描述：

第一行两个整数n和V，表示物品个数和背包体积。

接下来n行，每行两个数vi和wi，表示第i个物品的体积和价值。

1≤n,V;vi,wi≤1000

输出描述：

输出有两行，第一行输出第一问的答案，第二行输出第二问的答案，如果无解请输出0。

示例1

输入：

输出：

复制

说明：

示例2

输入：

输出：

说明：

思路

第一问：

状态表示：
- 表示从前个物品中挑选，总体积不超过的情况下，所有的选法中能挑选出的最大价值。
状态转移方程：
- 对于每个物品，我们有两种选择：
  - 不选第个物品：此时。
  - 选择第个物品：此时需要确保总体积不超过，而且该状态是合法的，即和存在。状态转移方程为。
初始化：
- 多加一行，第一行初始化为，因为不选任何物品总体积为时，价值为。
填表顺序：
- 从上往下，每一行从左往右填表。
返回值：
- 返回，即最后一行最后一列的值。

第二问：

状态表示：
- 表示从前个物品中挑选，总体积正好等于的情况下，所有的选法中能挑选出的最大价值。
状态转移方程：
- 。
- 在使用时，需要判断和是否为。
初始化：
- 多加一行，第一格初始化为，表示正好凑齐体积为的背包。
- 第一行后面的格子初始化为，因为没有物品，无法满足体积大于的情况。
填表顺序：
- 从上往下，每一行从左往右填表。
返回值：
- 由于最后可能凑不成体积为的情况，需要特判。

代码

优化步骤：

滚动数组的应用：
- 在01背包问题中，通过滚动数组可以删去所有的横坐标，因为状态只依赖于上一行的状态和，因此只需保留一行状态。
遍历顺序修改：
- 修改了的遍历顺序，原本的遍历是从到，现在改为从到。这样做的原因是，如果从到遍历，会使用当前行的的值，而我们已经在上一步的滚动数组中删除了这一行，所以需要改变遍历顺序，从到。

题目链接：https://leetcode.cn/problems/partition-equal-subset-sum/

给你一个 只包含正整数 的非空数组。请你判断是否可以将这个数组分割成两个子集，使得两个子集的元素和相等。

示例 1：

示例 2：

提示：

思路

状态表达：
- 表示在前个元素中选择，所有的选法中，能否凑成总和为这个数。
状态转移方程：
- 根据最后一个位置的元素，分两种情况讨论：
  - 不选择：此时是否能够凑成总和为取决于前个元素的情况，即。
  - 选择：如果小于等于，则需要看前个元素中是否能凑成总和为，即。
初始化：
- 第一行表示不选择任何元素，要凑成目标和，只有当目标和为时才能做到，因此第一行仅需初始化第一个元素。
填表顺序：
- 根据状态转移方程，从上往下填写每一行，每一行的顺序是无所谓的。
返回值：
- 根据状态表达，返回的值，其中表示数组的大小，表示要凑的目标和。
空间优化：
- 对于 01 背包类型的问题，可以进行空间上的优化，即删除第一维，并修改第二层循环的遍历顺序。

代码

空间优化

题目链接：https://leetcode.cn/problems/target-sum/

给你一个非负整数数组和一个整数。

向数组中的每个整数前添加或，然后串联起所有整数，可以构造一个 表达式 ：

例如，，可以在之前添加，在之前添加，然后串联起来得到表达式。

返回可以通过上述方法构造的、运算结果等于的不同 表达式 的数目。

示例 1：

示例 2：

提示：

思路

状态表示：
- 表示在前个数中选，总和正好等于，一共有多少种选法。
状态转移方程：
- 根据最后一个位置的元素，结合题目的要求，有两种策略：
  - 不选：此时凑成总和的总方案数，要看在前个元素中选，凑成总和为的方案数，即。
  - 选择：如果小于等于，则需要看前个元素中是否能凑成总和为，即。
初始化：
- 需要用到上一行的数据，因此初始化第一行，表示不选择任何元素凑成目标和。只有当目标和为时才能做到，因此第一行仅需初始化第一个元素。
填表顺序：
- 根据状态转移方程，从上往下填写每一行，每一行的顺序是无所谓的。
返回值：
- 根据状态表示，返回的值，其中表示数组的大小，表示要凑的目标和。

代码

题目链接：https://leetcode.cn/problems/last-stone-weight-ii/

有一堆石头，用整数数组表示。其中表示第块石头的重量。

每一回合，从中选出任意两块石头，然后将它们一起粉碎。假设石头的重量分别为和，且。那么粉碎的可能结果如下：

如果，那么两块石头都会被完全粉碎；
如果，那么重量为的石头将会完全粉碎，而重量为的石头新重量为。

最后，最多只会剩下一块 石头。返回此石头 最小的可能重量 。如果没有石头剩下，就返回。

示例 1：

示例 2：

提示：

思路

状态表示：
- 表示在前个元素中选择，总和不超过的情况下，这些元素的最大和。
状态转移方程：
- 根据最后一个位置的元素，结合题目的要求，有两种策略：
  - 不选：此时是否能够凑成总和为，要看在前个元素中选，能否凑成总和为。根据状态表示，此时。
  - 选择：这种情况下是有前提条件的，此时的应该是小于等于。因为如果这个元素都比要凑成的总和大，选择它就没有意义。那么是否能够凑成总和为，要看在前个元素中选，能否凑成总和为。根据状态表示，此时。
初始化：
- 由于需要用到上一行的数据，可以先将第一行初始化。
- 第一行表示「没有石头」，因此想凑成目标和的最大和都是。
填表顺序：
- 根据状态转移方程，从上往下填写每一行，每一行的顺序是无所谓的。
返回值：
- 根据状态表示，找到最接近的最大和。
- 返回，因为我们要的是两堆石头的差。

代码

上一篇：单片机c语言轻松入门

下一篇：数据库连接池和dbutils讲解

版权声明：
本文来源网络，所有图片文章版权属于原作者，如有侵权，联系删除。

本文网址：https://www.mushiming.com/mjsbk/2390.html

相关文章：