题解 | #购物单#

/*/
一、思路：1、常规动态规划；
2、将子物品另外存放，不单独dp遍历，在dp遍历到父物品时，将所有子物品在一同父物品遍历。
二、其中有两个子物品的父物品遍历思路如下：
①只购买一个父物品；
②父物品和某一个子物品；
③父物品和另一个子物品；
④父物品和两个子物品；
⑤最后将所有情况比较大小即可。
三、因情况过多，代码可能过长。因此，可以考虑在dp循环中使用continue，更适合本题实际情况，来减少代码复杂度。
/*/

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int all = in.nextInt(), n = in.nextInt();
        int w[] = new int[n], v[] = new int[n], st[] = new int[n];//存储价格、重要度、是否是子物品；
        ArrayList<Integer> list[] = new ArrayList[n];//存储子物品；
        int ans[] = new int[all + 1];//一维滚动数组存储答案；
        for(int sa = 0; sa < n; sa ++) list[sa] = new ArrayList<Integer>();//初始化；
        for(int sa = 0; sa < n; sa ++){
            w[sa] = in.nextInt(); v[sa] = in.nextInt();
            int tim = in.nextInt();
            st[sa] = tim;
            if(tim == 0) continue;
            list[tim - 1].add(sa);
        }//记忆数据；

        for(int sa = 0; sa < n; sa ++){//双重for循环dp；
            for(int wq = all; wq >= 0; wq --){
                if(w[sa] > wq || st[sa] != 0) continue;//筛选掉子物品和超重物品；
                ans[wq] = Math.max(ans[wq], ans[wq - w[sa]] + v[sa] * w[sa]);
                if(list[sa].size() == 0) continue；//筛选掉没有子物品的父物品；
                int ind = list[sa].get(0);
                if(w[sa] + w[ind] <= wq)//筛选掉超重物品，此时不能用continue，防止跳走导致少遍历一种情况
                    ans[wq] = Math.max(ans[wq], ans[wq - w[sa] - w[ind]] + v[sa] * w[sa] + v[ind] * w[ind]);
                if(list[sa].size() == 1) continue;//筛选掉只有一个子物品的父物品；
                int ind2 = list[sa].get(1);
                if(w[sa] + w[ind2] > wq) continue;//继续添加限制条件，筛选掉超重的物品；
                ans[wq] = Math.max(ans[wq], ans[wq - w[sa] - w[ind2]] + v[sa] * w[sa] + v[ind2] * w[ind2]);
                if(w[sa] + w[ind2] + w[ind] > wq) continue;//继续筛选掉超重物品；
                ans[wq] = Math.max(ans[wq], ans[wq - w[sa] - w[ind] - w[ind2]] + v[sa] * w[sa] + v[ind2] * w[ind2] + v[ind] * w[ind]);
            }
        }

        System.out.println(ans[all]);//输出答案。
    }
}