一、0/1背包问题
问题描述：有n件物品和容量为m的背包 给出i件物品的重量以及价值 求解让装入背包的物品重量不超过背包容量 且价值最大 。
特点:这是最简单的背包问题，特点是每个物品只有一件供你选择放还是不放。
① 二维解法
设f[i][j]表示前 i 件物品 总重量不超过 j 的最大价值 可得出状态转移方程
f[i][j]=max{f[i-1][j-a[i]]+b[i], f[i-1][j]}
代码：
for(int i=1;i<=n;i++)
for(int j=m;j>0;j--){
if(a[i]<=j)
f[i][j]=max(f[i-1][j],f[i-1][j-a[i]]+b[i]);
else f[i][j]=f[i-1][j];
}
在一些情况下 题目的数据会很大 因此f数组不开到一定程度是没有办法ac。
②一维解法
设f[j]表示重量不超过j公斤的最大价值 可得出状态转移方程
f[j]=max{f[j], f[j−a[i]]+b[i]}
代码：
for(int i=1;i<=n;i++){
for(int j=m;j>=a[i];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]}
代码：
for(int i=1;i<=n;i++)
for(int j = a[i];j <= m;j++){
f[j] = max(f[j], f[j-a[i]]+b[i]);
}
三、多重背包问题
问题描述：有n件物品和容量为m的背包 给出i件物品的重量以及价值 还有数量 求解让装入背包的物品重量不超过背包容量 且价值最大 。
特点 ：它与完全背包有类似点 特点是每个物品都有了一定的数量。
状态转移方程为：
f[j] = max{f[j], f[j−k∗a[i]]+k∗b[i]}
for(int i=1;i<=n;i++)
for(int j=m;j>=a[i];j--)
for(int k=0;k<=c[i];k++){
if(j-k*a[i]<0)break;
f[j] = max(f[j], f[j-k*a[i]]+k*b[i]);
}
实战：
题目一：
链接：https://leetcode-cn.com/problems/coin-change-2/ 力扣（LeetCode）
题目：给定不同面额的硬币和一个总金额。写出函数来计算可以凑成总金额的硬币组合数。假设每一种面额的硬币有无限个。
示例 1：
输入: amount = 5, coins = [1, 2, 5]
输出: 4
解释: 有四种方式可以凑成总金额:
5=5
5=2+2+1
5=2+1+1+1
5=1+1+1+1+1
class Solution {
public int change(int amount, int[] coins) {
int []dp=new int[amount+1];
dp[0]=1;
for(int coin:coins){
for(int i=coin;i<=amount;i++){
dp[i]=dp[i]+dp[i-coin];
}
}
return dp[amount];
}
}
