背包问题（完全背包）
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，使得物品价值最大。 此问题是完全背包问题，即 一个物品可重复出现。
三种基本背包问题
问题描述： 有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） 题目：给定不同面额的硬币和一个总金额。写出函数来计算可以凑成总金额的硬币组合数。假设每一种面额的硬币有无限个。
背包问题和0-1背包问题有什么区别
背包问题和0－1背包问题区别为：循环变量不同、约束条件不同、最大总价值不同。一、循环变量不同1、背包问题：背包问题须先求出列坐标j较小的元素，故让循环变量j的值从小到大递增。2、0－1背包问题：0－1背包问题须先求出列坐标j较大的元素，故让循环变量j的值从大到小递减。二、约束条件不同1、背包问题：背包问题的约束条件是给定几种物品，物品可以取无限次。2、0－1背包问题：0－1背包问题的约束条件是给定几种物品，物品只可以取一次。三、最大总价值不同1、背包问题：背包问题若取了1件第i个物品，则总容量变为j－W［i］，剩下的仍可以在前i件物品中去取，其最大总价值为B［i］［j－W［i］］ ＋ P［i］。2、0－1背包问题：0－1背包问题若取了1件第i个物品，则总容量变为j－W［i］，剩下的只能在前i－1件物品中去取了，其最大总价值为B［i－1］［j－W［i］］ ＋ P［i］。