题解 | #购物单#

import java.util.Scanner;

// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int budget = in.nextInt();
        int quantity = in.nextInt();
        Item[] items = new Item[quantity];
        for(int i = 0; i < quantity; i++){
            items[i] = new Item();
        }
        int maxSatisfy = 0;
        
        for (int i = 0; i < quantity; i++) {
            int price = in.nextInt();
            int important = in.nextInt();
            int parent = in.nextInt();
            items[i].important = important;
            items[i].price = price;
            items[i].parent = parent;
            if (parent != 0) {
                if (items[parent-1].sub1 == -1) {
                    items[parent-1].sub1 = i;
                } else {
                    items[parent-1].sub2 = i;
                }

            }
        }
        int[][] qb = new int[quantity+1][budget+1];
        for (int i = 1; i <= quantity; i++) {
            int satisfyMainSub1 = 0, satisfyMainSub2 = 0, satisfyMainSub1Sub2 = 0;
            int priceMain = 0, priceMainSub1 = 0, priceMainSub2 = 0, priceMainSub1Sub2 = 0;
            Item item = items[i-1];
            // only main
            int satsfyMain = item.getSatisfy();
            priceMain = item.price;
            if (item.sub1 >= 0) {
                // main + sub1
                priceMainSub1 = priceMain + items[item.sub1].price;
                satisfyMainSub1 = satsfyMain + items[item.sub1].getSatisfy();
            }
            if (item.sub2 >= 0) {
                // main + sub2
                priceMainSub2 = priceMain + items[item.sub2].price;
                satisfyMainSub2 = satsfyMain + items[item.sub2].getSatisfy();
            }
            // main + sub1 + sub2
            if (item.sub1 >= 0 && item.sub2 >= 0) {
                priceMainSub1Sub2 = priceMain + items[item.sub1].price + items[item.sub2].price;
                satisfyMainSub1Sub2 = satsfyMain + items[item.sub1].getSatisfy() +
                                      items[item.sub2].getSatisfy();
            }
            
            for (int j = 0; j <= budget; j++) {
                if (item.parent == 0) {
                    qb[i][j] = qb[i-1][j];
                    if(j>=priceMain)
                        qb[i][j] = Math.max(qb[i][j], qb[i-1][j - priceMain]+satsfyMain);
                    if(j>=priceMainSub1&&item.sub1 >= 0)
                        qb[i][j] = Math.max(qb[i][j], qb[i-1][j - priceMainSub1]+satisfyMainSub1);
                    if(j>=priceMainSub2&&item.sub2 >= 0)
                        qb[i][j] = Math.max(qb[i][j], qb[i-1][j - priceMainSub2]+satisfyMainSub2);
                    if(j>=priceMainSub1Sub2&&item.sub1 >= 0 && item.sub2 >= 0)
                        qb[i][j] = Math.max(qb[i][j], qb[i-1][j - priceMainSub1Sub2]+satisfyMainSub1Sub2);

                } else {
                    qb[i][j] = qb[i-1][j];
                }


            } 
        }
        System.out.println(qb[quantity][budget]);
    }
}
class Item {
    int important;
    int price;
    int parent;
    int sub1=-1;// sub1 index
    int sub2=-1;// sub2 index(other item parent-1)

    public int getSatisfy() {
        return important * price;
    }
}

借鉴了别人的， 动态算法， 妙啊

如用例

1000 5

300 5 0

400 2 0

300 5 2

300 4 2

600 4 0

当计算完物品1价值后： 得到的最大满意度是物品1的最大满意度

当计算完物品1，物品2（由于物品2 有两个子类，需要同时计算）后： 得到的最大满意度是对应价值能购买到的物品的最大满意度之和。所以到价值是600时，由于其购买到的物品2价值=800，相比若购买物品1价值=1500满意度低，所以取满意度最大值1500。 但是当价值为700时，其可购买物品2+物品2子类1达到满意度2300，故当700 时， 满意度=2300. 其对应的公式为

首先设置dp[2][700] = dp[1][700]

dp[2][700] = Math.max(dp[2][700],dp[2][1000-700] + 物品2满意度) = Math.max(1500, 1500+800) = 2300

物品2满意度的可能性有4种， 物品2， 物品2+子类1， 物品2+子类2，物品2+子类1+子类2； 记录对应的钱数，当钱数小于总价格时， 可以通过比较拿到对应位置的最大满意度。

计算完物品3同理。