题目：
思路： 0-1 背包
背包两个属性：容量W和N个物品（N个数一般等于物品数量，即 状态 i ）
限定的是什么钱，即钱就是限定的容量W，对应物品单价就是wt
求最多买多少口罩，即口罩的个数就是val值；
初始化 dp[N+1][W+1]，
dp定义：最终所求为 dp[N][W]即对前 i 个物品进行选择，【在容量为 w时】，可以装的最大价值是 dp[i][w]；
basecase：
base case 就是 dp[0][…] = dp[…][0] = 0，即没有物品和没有容量时，背包装的价值为0；但数组会自动初始化为0；
状态： i 为物品序号， w为每种容量；
状态转移：
求以下两种的最大值：
1.不装入 i 物品，dp[i][w]=dp[i-1][w] ;
2.装入 i 物品，dp[i][w]=dp[i-1][w-wt[i]]+val[i] ，即前i-1个物品相当于放到了容量为 w – wt[i-1]]的背包里！
注意：
i =0 是base case , 所以遍历状态要从 i=1 开始！
import java.util.Scanner;
public class Main{
public static void main(String[] args){
Scanner in=new Scanner(System.in);
int W=in.nextInt();
// 限定了N元，即价格是背包容量
int[] wt={0,2,2,3,1,5,2};
// 求最多多少口罩，即口罩个数是价值
int[] val={0,2,3,1,5,4,3};
int N=6;
int[][] dp=new int[n+1][W+1]; // 会初始化为全0
// i=0 和w=0 都无效，都是0 ！
for(int p=0;p<=W;p++){
dp[0][p]=0; //没有物品
}
for(int q=0;q<=N;q++){
dp[q][0]=0;//没有容量
}
//
for(int i=1;i<=N;i++){//遍历每个物品（序号）
for(int w=1;w<=W;w++){ //遍历每种容量大小
if(w<wt[i]){ //当前容量w小于了物品i需要的容量，则一定不放背包
dp[i][w]=dp[i-1][w];
}else{ // 放入和不放入，选最大
dp[i][w]=Math.max( dp[i-1][w] , dp[i-1][w-wt[i]]+val[i]);
}
}
}
System.out.println(dp[N][W]);
}
}
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 举报，一经查实，本站将立刻删除。
文章由极客之音整理，本文链接：https://www.bmabk.com/index.php/post/89203.html
