三种基本背包问题
问题描述： 有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）
题目：给定不同面额的硬币和一个总金额。写出函数来计算可以凑成总金额的硬币组合数。假设每一种面额的硬币有无限个。
