题解 | #购物单#
题目：
1.选择了附件，则必须要选择其对应主件；
2.选择了主件后，选不选附件，选几个附件，取决于满足N的条件下，<金额*满意度>的变化情况；
3.在总金额为N的条件下，选选取<金额*满意度>的场景；
p[i][j]的含义：从下标为[0-i]的物品里任意取、任意取、任意取，放进容量为j的背包，代表的价值总和。背包问题的核心在下面的状态转移过程，dp[i][j]是由dp[i-1][j] dp[i-1][j-weight]得来的。
for(int i = 1; i < weight.size(); i++) { // 遍历物品
for(int j = 0; j <= bagWeight; j++) { // 遍历背包容量
if (j < weight[i]) { // j 小于 i的重量，因此不能放入i
dp[i][j] = dp[i - 1][j];
}
else { // j >= i的重量，因此可以选择放入i
dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - weight[i]] + value[i]);
}
}
}
完整代码如下：
import java.util.*;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
while (sc.hasNextLine()) {
int money = sc.nextInt();
int m = sc.nextInt();
sc.nextLine();
money /= 10; // 题目规定都是10的倍数，可以减小空间消耗
int[][] prices = new int[m+1][3];
int[][] weights = new int[m+1][3];
for (int i = 1; i <= m; i++) {
int a = sc.nextInt(); // 价格
int b = sc.nextInt(); // 重要度
int c = sc.nextInt(); // 主附件
a /= 10;
b = b * a; // 题目要求的最优值是 重要度 * 价格
if (c == 0) { // 主件
prices[i][0] = a;
weights[i][0] = b;
} else if (prices[c][1] == 0) { // 附件1
prices[c][1] = a;
weights[c][1] = b;
} else { // 附件2
prices[c][2] = a;
weights[c][2] = b;
}
sc.nextLine();
}
// dp[i][j]表示在物品0-i之间取任意物品，背包容量为j时的最优值
int[][] dp = new int[m+1][money+1];
for (int i = 1; i <= m; i++) {
for(int j = 1; j <= money; j++) {
// 主件
int a = prices[i][0];
int b = weights[i][0];
// 附件1
int c = prices[i][1];
int d = weights[i][1];
// 附件2
int e = prices[i][2];
int f = weights[i][2];
// 针对物品i，有以下判断：
// j > a，则背包可以装下：主件
dp[i][j] = j-a >= 0 ? Math.max(dp[i-1][j], dp[i-1][j-a] + b) : dp[i-1][j];
// j > a+c，则背包可以装下：主件 + 附件1（主件基础上加附件1）
dp[i][j] = j-a-c >= 0 ? Math.max(dp[i][j], dp[i-1][j-a-c] + b + d) : dp[i][j];
// j > a+e，则背包可以装下：主件 + 附件2（主件基础上加附件2）
dp[i][j] = j-a-e >= 0 ? Math.max(dp[i][j], dp[i-1][j-a-e] + b + f) : dp[i][j];
// j > a+c+e，则背包可以装下：主件 + 附件1 + 附件2（主件基础上加附件1和附件2）
dp[i][j] = j-a-c-e >= 0 ? Math.max(dp[i][j], dp[i-1][j-a-c-e] + b + d + f) : dp[i][j];
}
}
System.out.println(dp[m][money] * 10);
}
}
}
快手公司福利 726人发布
