1. 题目
读题
考查点
01背包 变种
2. 解法
思路
代码逻辑
具体实现
import java.util.Scanner;
//定义一个物品类，用来存储每个物品的信息
class Good {
int v; //物品价格
int vp; //物品重要度乘价格
int q; //物品是否为主件
int a1; //附件1的编号
int a2; //附件2的编号
public Good(int v, int p, int q) {
this.v = v;
this.vp = v * p;
this.q = q;
this.a1 = 0;
this.a2 = 0;
}
}
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int N = sc.nextInt(); //总钱数
int m = sc.nextInt(); //物品个数
Good[] goods = new Good[m + 1]; //创建一个物品数组，下标从1开始
for (int i = 1; i <= m; i++) {
int v = sc.nextInt(); //物品价格
int p = sc.nextInt(); //物品重要度
int q = sc.nextInt(); //物品是否为主件
goods[i] = new Good(v, p, q); //创建一个物品对象，存入数组中
if (q > 0) { //如果是附件，就将其编号存入对应主件的属性中
if (goods[q].a1 == 0) {
goods[q].a1 = i;
} else {
goods[q].a2 = i;
}
}
}
int[][] dp = new int[m + 1][N + 1]; //创建一个二维数组，用来表示动态规划的状态
for (int i = 1; i <= m; i++) { //遍历每个物品
int v0, v1, v2, v3; //分别表示只买主件、买主件和附件1、买主件和附件2、买主件和附件1和附件2的总价格
int vp0, vp1, vp2, vp3; //分别表示只买主件、买主件和附件1、买主件和附件2、买主件和附件1和附件2的总满意度
v0 = goods[i].v; //只买主件的总价格就是主件价格
vp0 = goods[i].vp; //只买主件的总满意度就是主件重要度乘价格
v1 = v0 + goods[goods[i].a1].v; //买主件和附件1的总价格就是主件价格加附件1价格
vp1 = vp0 + goods[goods[i].a1].vp; //买主件和附件1的总满意度就是主件重要度乘价格加附件1重要度乘价格
v2 = v0 + goods[goods[i].a2].v; //买主件和附件2的总价格就是主件价格加附件2价格
vp2 = vp0 + goods[goods[i].a2].vp; //买主件和附件2的总满意度就是主件重要度乘价格加附件2重要度乘价格
v3 = v0 + goods[goods[i].a1].v + goods[goods[i].a2].v; //买主件和附件1和附件2的总价格就是主件价格加附件1价格加附件2价格
vp3 = vp0 + goods[goods[i].a1].vp + goods[goods[i].a2].vp; //买主件和附件1和附件2的总满意度就是主件重要度乘价格加附件1重要度乘价格加附件2重要度乘价格
for (int j = 1; j <= N; j++) { //遍历每个钱数
if (goods[i].q > 0) { //如果是附件，就不买，继承上一个物品的状态
dp[i][j] = dp[i - 1][j];
} else { //如果是主件，就比较四种方案中的最大满意度
dp[i][j] = dp[i - 1][j]; //默认不买当前物品
if (j >= v0) { //如果钱数大于等于只买主件的总价格，就比较不买和只买主件的满意度
dp[i][j] = Math.max(dp[i][j], dp[i - 1][j - v0] + vp0);
}
if (j >= v1 && goods[i].a1 > 0) { //如果钱数大于等于买主件和附件1的总价格，且附件1存在，就比较不买、只买主件和买主件和附件1的满意度
dp[i][j] = Math.max(dp[i][j], dp[i - 1][j - v1] + vp1);
}
if (j >= v2 && goods[i].a2 > 0) { //如果钱数大于等于买主件和附件2的总价格，且附件2存在，就比较不买、只买主件、买主件和附件1和买主件和附件2的满意度
dp[i][j] = Math.max(dp[i][j], dp[i - 1][j - v2] + vp2);
}
if (j >= v3 && goods[i].a1 > 0 && goods[i].a2 > 0) { //如果钱数大于等于买主件和附件1和附件2的总价格，且附件1和附件2都存在，就比较不买、只买主件、买主件和附件1、买主件和附件2和买主件和附件1和附件2的满意度
dp[i][j] = Math.max(dp[i][j], dp[i - 1][j - v3] + vp3);
}
}
}
}
System.out.println(dp[m][N]); //输出最大满意度
}
}