动态规划讲解
https://tangshusen.me/2019/11/24/knapsack-problem/
0/1背包
//01背包问题伪代码（空间优化版）
dp[0,...,W]=0;
for i=1,...,N
for j=W,...w[i]//必须逆向枚举!!!
dp[j]=max(dp[j],dp[j-w[i]]+v[i])
//完全背包问题思路伪代码（空间优化）
dp[0,...,W]=0;
for i=1,...,N
for j=w[i],...,W//必须正向枚举！！！
dp[j]=max(dp[j],dp[j-w[i]]+v[i])
//恰好装满要注意初始化值，重量为0时最大价值为0，dp[0]=0;而当重量不为0时，暂时不知道最大价值，但是由于后面要max，所以初始化Integer.MIN_VALUE;
//求方案数总和
时间复杂度O(NW),空间复杂度O(W)
package com.dj;
import java.util.Arrays;
public class test {
// 所有的物品
private Knapsack[] bags;
// 物品的数量
private int n;
// 背包总承重
private int totalWeight;
// 第一维：当前第几个物品；第二维：当前的背包承重；值：当前背包最大价值
private int[][] bestValues;
private int[] res;
// 最终背包中最大价值
private int bestValue;
public test(Knapsack[] bags, int totalWeight) {
this.bags = bags;
this.totalWeight = totalWeight;
this.n = bags.length;
if (bestValues == null) {
// 考虑0的状态+1，防止数组角标越界
bestValues = new int[n + 1][totalWeight + 1];
}
if(res==null){
res=new int[totalWeight+1];
}
}
public void solve2(){
//对一维数组F进行初始化，即当背包不放入物品，其最大价值均为0
for(int i=0;i<=totalWeight;i++){
res[i]=0;
}
for(int i = 1; i <= n; i++){
for(int j=totalWeight;j>=0;j--){
if(j>=bags[i-1].getWeight()){
res[j]=Math.max(res[j],res[j-bags[i-1].getWeight()]+bags[i-1].getValue());
}else{//可省略
res[j]=res[j];
}
}
}
System.out.println(res[totalWeight]);
}
public void solve() {
// 遍历背包的承重
for (int j = 0; j <= totalWeight; j++) {
// 遍历指定物品
for (int i = 0; i <= n; i++) {
// 当背包不放入物品或承重为0时，其最大价值均为0
if (i == 0 || j ==