题解 | #购物单# 01背包扩展,可读性强解法
购物单
https://www.nowcoder.com/practice/f9c6f980eeec43ef85be20755ddbeaf4
- 核心: dp[i] = max(dp[i], dp[i-主件], dp[i-主件-附件1], dp[i-主件-附件2], dp[i-主件-附件1-附件2])
import java.util.*; // 注意类名必须为 Main, 不要有任何 package xxx 信息 public class Main { public static class Item { int id; int mainId; // 附件才有 int p; int v; // p * itemValue Item sub1; Item sub2; } // 每个主件可以有 0 个、 1 个或 2 个附件!! // items.size() < 60 // limitMoney < 32000 // dp[i] = max(dp[i], dp[i-主件], dp[i-主件-附件1], dp[i-主件-附件2], dp[i-主件-附件1-附件2]) static int getMaxSatisfyValue(Map<Integer, Item> items, int limitMoney) { int[] dp = new int[limitMoney + 1]; for (Item item : items.values()) { for (int i = limitMoney; i >= item.p; i--) { // 尝试买当前物品, 倒着防重复 dp[i] = Math.max(dp[i], dp[i - item.p] + item.v); if (item.sub1 != null) { int idx = i - item.p - item.sub1.p; if (idx >= 0) { dp[i] = Math.max(dp[i], dp[idx] + item.v + item.sub1.v); } } if (item.sub2 != null) { int idx = i - item.p - item.sub2.p; if (idx >= 0) { dp[i] = Math.max(dp[i], dp[idx] + item.v + item.sub2.v); } } if (item.sub1 != null && item.sub2 != null) { int idx = i - item.p - item.sub1.p - item.sub2.p; if (idx >= 0) { dp[i] = Math.max(dp[i], dp[idx] + item.v + item.sub1.v + item.sub2.v); } } } } return dp[limitMoney]; } public static void main(String[] args) { Scanner in = new Scanner(System.in); int limitMoney = in.nextInt(); int itemCount = in.nextInt(); List<Item> itemList = new ArrayList<>(itemCount); Map<Integer, Item> items = new HashMap<>(); for (int id = 1; id <= itemCount; id++) { int p = in.nextInt(); int value = in.nextInt(); int mainId = in.nextInt(); Item item = new Item(); item.id = id; item.mainId = mainId; item.p = p; item.v = value * p; itemList.add(item); if (mainId == 0) { items.put(item.id, item); } } for (Item item : itemList) { if (item.mainId > 0) { Item mainItem = items.get(item.mainId); if (mainItem.sub1 == null) { mainItem.sub1 = item; } else { mainItem.sub2 = item; } } } int res = getMaxSatisfyValue(items, limitMoney); System.out.println(res); } }#经典01背包问题稍作修改就可以得出这题的解答#