背包问题 动态规划 三种基本背包问题

问题描述： 有n件物品和容量为m的背包 给出i件物品的重量以及价值 还有数量 求解让装入背包的物品重量不超过背包容量 且价值最大 。 特点 ： 它与完全背包有类似点 特点是每个物品都有了 一定的数量 。

文章目录：

1. 三种基本背包问题
2. 背包问题(完全背包)

一、三种基本背包问题

问题描述： 有n件物品和容量为m的背包 给出i件物品的重量以及价值 求解让装入背包的物品重量不超过背包容量 且价值最大 。

特点: 这锋段是最简单的背包问题，特点是每个物品只有一件供你选择放还是不放。

① 二维解法

设f[i][j]表示前 i 件物品 总重量不超过 j 的最大价值 可得出状态转移方程

f[i][j]=max{f[i-1][j-a[i]]+b[i], f[i-1][j]}

在一些情况下 题目的数据会很大 因此f数组不开到一定程度是没有办法ac。

②一维解法

设f[j]表示重量不超过j公斤的最大价值 可得出状态转移方程

f[j]=max{f[j], f[j−a[i]]+b[i]}

问题描述： 有n件物品和容量为m的背包 给出i件物品的重量以及价值 求解让装入背包的物品重量不超过背包容量 且价值最大 。

特点： 题干看似与01一样 但它的特点是每个物品可以 无限选用 。

设f[j]表示重量不超过j公斤的最大价值 可得出状态转移方程

f[j] = maxj{f[j], f[j−a[i]]+b[i]}

问题描述： 有n件物品和容量为m的背包 给出i件物品的重量以镇衫及价值 还有数量 求解让装入背包的物品重量不超过背包容量 且价值最大 。

特点 ： 它与完全背包有类似点 特点是每个物品都有了 一定的数量 。

状态转移方程为：

f[j] = max{f[j], f[j−k∗a[i]]+k∗b[i]}

题目一：银旅誉

链接： https://leetcode-cn.com/problems/coin-change-2/ 力扣（LeetCode）

题目：给定不同面额的硬币和一个总金额。写出函数来计算可以凑成总金额的硬币组合数。假设每一种面额的硬币有无限个。

二、背包问题(完全背包)

1.矩阵链乘法

2.投资组合问题

3.完全背包问题

4.01背包问题

5.最长公共子序列

一个背包，可以放入n种物品，物品j的重量和价值分别为 ，如果背包的最大重量限制是b，怎么样选择放入背包的物品以使得背包的总价值最大？

组合优化问题，设 表示装入背包的第j个物品的数量，解可以表示为 。那么目标函数和约束条件是：

如果组合优化问题的目标函数和约束条件都是线性函数，称为线性规划。如果线性规划问题的变量 都是非负整数，则称为整数规划问题。背包问题就是整数规划问题。限制所有的 时称为0-1背包

子问题的界定（就是靠什么来划分子问题）：由参数k和y界定

k：考虑对物品1,2,3,...,k的选择。

y：表示背包总重

子问题计算顺序：k=1,2,...,k，对给定的k，y=1,2,...,b

：装前k个物品，重量不超过y时的背包最大值。

包含两种情况：不装第k种物品或至少装一件第k种物品。

对 的解释：装一件第k种物品后，最优的解法仍然是在前k个物品进行选择，仍陵圆有可能再选入1件第k种物品。

对边界条件:

：即只用第一种物品背包重量限制为y的最大价值，为了保证背包不超重，第一种物品至多能装 个，因为背包价值为

有些 那么通过设置为负无穷，在选择过程中抛弃掉为负的情况。

标记磨辩函数：用来追踪解

按照递推公式：以k=2为例子，简单演算如下：

依次类推，可得备忘录表：

标记函数的备忘录：

物品受限背包 ：第i种物品最多用 个

0-1背包问题 ：

多背包 ：m个背包，背包 装入最大重量 在满足所有背包重量约束下使物品价值最尺游塌大。

二维背包 ：每件物品重量 和体积 ，背包总重不超过b，体积不超过V，使得物品价值最大。

此问题是完全背包问题，即 一个物品可重复出现。

以上是问答百科为你整理的2条关于背包问题的问题，希望对你有帮助！更多相关背包问题的内容请站内查找。