描述

王強今天很開心，公司發(fā)給N元的年終獎。王強決定把年終獎用于購物，他把想買的物品分為兩類：主件與附件，附件是從屬于某個主件的，下表就是一些主件與附件的例子：

主件 附件
電腦 打印機，掃描儀
書柜 圖書
書桌 臺燈，文具
工作椅 無

如果要買歸類為附件的物品，必須先買該附件所屬的主件。每個主件可以有 0 個、 1 個或 2 個附件。附件不再有從屬于自己的附件。王強想買的東西很多，為了不超出預算，他把每件物品規(guī)定了一個重要度，分為 5 等：用整數(shù) 1 ~ 5 表示，第 5 等最重要。他還從因特網(wǎng)上查到了每件物品的價格（都是 10 元的整數(shù)倍）。他希望在不超過 N 元（可以等于 N 元）的前提下，使每件物品的價格與重要度的乘積的總和最大。
設第 j 件物品的價格為 v[j] ，重要度為 w[j] ，共選中了 k 件物品，編號依次為 j 1 ， j 2 ，……， j k ，則所求的總和為：
v[j 1 ]w[j 1 ]+v[j 2 ]w[j 2 ]+ … +v[j k ]*w[j k ] 。（其中 * 為乘號）
請你幫助王強設計一個滿足要求的購物單。

輸入描述：

輸入的第 1 行，為兩個正整數(shù)，用一個空格隔開：N m
（其中 N （ <32000 ）表示總錢數(shù)， m （ <60 ）為希望購買物品的個數(shù)。）
從第 2 行到第 m+1 行，第 j 行給出了編號為 j-1 的物品的基本數(shù)據(jù)，每行有 3 個非負整數(shù) v p q
（其中 v 表示該物品的價格（ v<10000 ）， p 表示該物品的重要度（ 1 ~ 5 ）， q 表示該物品是主件還是附件。如果 q=0 ，表示該物品為主件，如果 q>0 ，表示該物品為附件， q 是所屬主件的編號）

輸出描述：

輸出文件只有一個正整數(shù)，為不超過總錢數(shù)的物品的價格與重要度乘積的總和的最大值（ <200000 ）。

輸入輸出示例

輸入：

1000 5
800 2 0
400 5 1
300 5 1
400 3 0
500 2 0

輸出：

2200

動態(tài)規(guī)劃題解：

import java.util.Arrays;
import java.util.HashSet;
import java.util.Scanner;
import java.util.stream.Stream;


public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int money = in.nextInt();
        int num = in.nextInt();
        int[][][] goods = new int[num][3][3];
        int i = 0;
        // 標記指定編號的主件是否已有附件
        HashSet<Integer> attachExists = new HashSet<>();
        while (i < num) {
            int p = in.nextInt();
            int v = in.nextInt();
            int f = in.nextInt();
            if (f == 0) {
                goods[i][0] = new int[]{p, v};
            } else {
                // 如果指定編號主件沒有附件，放在主件后第一位置
                if (!attachExists.contains(f - 1)) {
                    goods[f - 1][1] = new int[]{p, v};
                    attachExists.add(f - 1);
                }
                // 如果指定編號主件有附件，放在主件后第一位置
                else {
                    goods[f - 1][2] = new int[]{p, v};
                }
            }
            i++;
        }
        // 過濾掉非主件位置的空good
        Stream<int[][]> filteredGoods = Arrays.stream(goods).filter(good -> good[0][0] != 0);
        // 設置初始狀態(tài)
        int[] init = new int[money + 1];
        init[0] = 0;
        // 外層循環(huán)商品
        filteredGoods.forEach(good -> {
            // 類似01背包，為避免重復選擇，需倒序遍歷
            for (int m = money; m > 0; m--) {
                // 如果主件價格小于當前錢數(shù)，只選主件
                if (good[0][0] <= m) {
                    init[m] = Math.max(init[m], init[m - good[0][0]] + good[0][0] * good[0][1]);
                }
                // 如果附件1存在，且主件價格和附件1的價格之和小于當前錢數(shù)，選擇主件和附件1
                if (good[1][0] != 0 && good[0][0] + good[1][0] <= m) {
                    init[m] = Math.max(init[m], init[m - good[0][0] - good[1][0]] + good[0][0] * good[0][1] + good[1][0] * good[1][1]);
                }
                // 如果附件2存在，且主件價格和附件2的價格之和小于當前錢數(shù)，選擇主件和附件2
                if (good[2][0] != 0 && good[0][0] + good[2][0] <= m) {
                    init[m] = Math.max(init[m], init[m - good[0][0] - good[2][0]] + good[0][0] * good[0][1] + good[2][0] * good[2][1]);
                }
                // 如果附件1和2都存在，且主件價格和附件1,2的價格之和小于當前錢數(shù)，選擇主件和附件1,2
                if (good[1][0] != 0 && good[2][0] != 0 && good[0][0] + good[1][0] + good[2][0] <= m) {
                    init[m] = Math.max(init[m], init[m - good[0][0] - good[1][0] - good[2][0]] + good[0][0] * good[0][1] + good[1][0] * good[1][1] + good[2][0] * good[2][1]);
                }
            }
        });
        System.out.println(init[money]);
    }
}