今天来个简单的背包问题大汇总
1. 01背包
01背包顾名思义就是对一种物品只有选或者不选两种选择
对于背包体积为W，物品数量是N，每个物品的体积是w[i]，每个物品的价值是price[i]的选择，求用这个背包装下的物品价值最大
dp[i][j]表示数量为i体积为j的时候选出的最大价值
方程：`dp[i][j]=Math.max(dp[i-1][j],dp[i][j-w[i]]+prices[i])`
public static void main(String[] args) {
int N=4;//物品数量
int W=5;//体积
int[] w={1,2,3,4};//每个物品体积
int[] prices={2,4,4,5};//每个物品价值
int[][] dp=new int[N+1][W+1];
for (int i = 1; i <= N; i++) {
for (int j = 1; j <= W ; j++) {
//在j比w[i-1]小的时候，选不了物品，所以只能dp[i][j]=dp[i-1][j];
if(j>=w[i-1]){
dp[i][j]=Math.max(dp[i-1][j],dp[i-1][j-w[i-1]]+prices[i-1]);
}else{
dp[i][j]=dp[i-1][j];
}
}
}
System.out.println(dp[N][W]);
}
优化：
上面的装态方程只与i-1有关，因此可将二维状态方程压缩成一维状态方程
方程：dp[j]=Math.max(dp[j],dp[j-w[i]]+prices[i])
但是这里按照j从小打到进行计算的话，背包会被重复计算（那就是后面的完全背包问题了），所以要从大到小进行计算
public static void main(String[] args) {
int N=4;//物品数量
int W=5;//体积
int[] w={1,2,3,4};//每个物品体积
int[] prices={2,4,4,5};//每个物品价值
int[] dp=new int[W+1];
for(int i=1;i<=N;i++){
for(int j=W;j>=1;j--){
if(j>=w[i-1]){
dp[j]=Math.max(dp[j],dp[j-w[i-1]]+prices[i-1]);
}
}
}
System.out.println(dp[W]);
}
之前一直不理解为什么j从小到大就会重复，这里引用一个例子
https://blog.csdn.net/qq_33279781/article/details/52073519
假设一个物品GG价值1000，体积为2，那么假设我们按【0…..v】这个顺序遍历，那么在j=2时，dp[2] = max(dp[2], dp[0]+1000)，那么dp[2] = 1000，当j=4时，dp[4]=max(dp[4], dp[2]+1000)， dp[4] = 2000，这时我们再思考一下，GG将被放进背包两次
2. 完全背包
完全背包指的就是物品的次数可以被无数次选取，非常好理解，就是之前的01背包的基础上，每个背包被重复选取，也就是我们的j从小到大的一个过程，每个背包被重复选取，求出最大值
public static void main(String[] args) {
int N=4;//物品数量
int W=5;//体积
int[] w={1,2,3,4};//每个物品体积
int[] prices={2,4,4,5};//每个物品价值
int[] dp=new int[W+1];
for(int i=1;i<=N;i++){
for(int j=w[i-1];j<=W;j++){
dp[j]=Math.max(dp[j],dp[j-w[i-1]]+prices[i-1]);
}
}
System.out.println(dp[W]);
}
3.多重背包
最简单的多重背包指的是背包能够被选取给定次数，同样的道理，在j从小到大的时候背包被无数次选取，选取次数不可控制，在01背包的基础上，j从大到小排列，每个背包只会被选取一次，在这个基础上，对每个j再加一重循环，使其被选取k次，就完成了多重背包
public static void main(String[] args) {
int N=4;//物品数量
int W=5;//体积
int[] w={1,2,3,4};//每个物品体积
int[] prices={2,4,4,5};//每个物品价值
int[] nums={3,1,3,2};
int[] dp=new int[W+1];
for(int i=1;i<=N;i++){
for(int j=W;j>=1;j--){
for (int k = 0; k <=nums[i-1]; k++) {
if(j>=k*w[i-1]){
dp[j]=Math.max(dp[j],dp[j-k*w[i-1]]+k*prices[i-1]);
}
}
}
}
System.out.println(dp[W]);
}
练习：leecode 322,416,518
