1、思路分析

如果这题把附件去掉，只考虑主件是不是跟01背包问题完全一样？。所以我也是想着怎么把附件给忽略掉。

最终的想法就是把主件和附件合在一起，它就是一个物品，只是这个物品会有不同的价格与满意度。

这个物品可能存在以下四个状态：

1、只有主件

2、主件+附件1

3、主件+附件2

4、主件+附件1+附件2

也就是说这是一个有不同状态的物品的背包问题。

2、解法

1、处理输入

 while (in.hasNextInt()) {
            int money = in.nextInt();
            int m = in.nextInt();

            int[] v = new int[m + 1];     //价值
            int[] p = new int[m + 1];     //重要度（临时算一下满意度，后面没用了）
            int[] q = new int[m + 1];     //是否附件
            int[] w = new int[m + 1];     //满意度

            for (int i = 1; i <= m; i++) {
                v[i] = in.nextInt();
                p[i] = in.nextInt();
                q[i] = in.nextInt();
                w[i] = v[i] * p[i];
            }
   //上面是处理输入，不是重点....................................
 }

2、把主件和附件合并

合并的方式有很多种，可以搞一个内部类，也可以用数组、列表这些，方便处理即可。我这里我是用的map和list。

goods：物品价值，key为物品编号，value为其几种状态的价值

weights：物品满意度，key为物品编号，value为其几种状态对应的满意度

因为主件和附件的顺序不知道，我只能遍历了两次，第一次把主件放进去了，第二次在主件的基础上添加附件同时更新各个状态的价值和满意度。

Map<Integer,List<Integer>> goods = new HashMap<>();     //物品价值，key为物品编号，value为其几种状态的价值
Map<Integer,List<Integer>> weights = new  HashMap<>();  //物品满意度，key为物品编号，value为其几种状态的满意度
            for (int i = 1; i <= m; i++) {
                if (q[i] == 0) {
                    //先放入主件
                    List<Integer> good = new ArrayList<>();
                    good.add(v[i]);
                    goods.put(i,good);
                    List<Integer> weight = new ArrayList<>();
                    weight.add(w[i]);
                    weights.put(i,weight);
                }
            }
            for (int i = 1; i <= m; i++) {
                if ( q[i] != 0) {
                    //再放附件，把主件对应的列表list拿出来去更新那几种状态
                    List<Integer> good = goods.get(q[i]);
                    List<Integer> weight = weights.get(q[i]);
                    int len = good.size();
                    for (int j = 0; j < len; j++) {
					  //更新价格和满意度
                        good.add(good.get(j) + v[i]);
                        weight.add(weight.get(j) + w[i]);
                    }
                }
            }

3、解题（在背包问题的基础上加一个循环，遍历物品的几种状态，去最大值）

1、首先看看背包问题的解法代码

//定义状态 dp[money] 表示钱为money时可以获得的最大满意度
int[] dp = new int[money+1];
//依次对每个物品进行处理
            for (int i = 1; i <= m; i++) {
                    for (int j = money; j >= v[i]; j-=10) {  //注意题目中说的都是10的倍数 
                        dp[j] = Math.max( dp[j-v[i] + w[i] , dp[j]) 
                    }
                }
            }

2、在其循环体，也就是状态转移过程中，增加一个遍历，取到最大值就行了。下面只对增加的那部分代码写注释。

int[] dp = new int[money+1]; 
            for (int i = 1; i <= m; i++) {
                if (q[i] == 0){//只处理主件
                    for (int j = money; j >= v[i]; j-=10) { 
                        List<Integer> good = goods.get(i);       //获取物品i不同状态的价值
                        List<Integer> weight = weights.get(i);   //同上，拿的是满意度
                        int max = dp[j];	//记录几种状态下的最大值
                        for (int k = 0; k < good.size(); k++) { //遍历物品的不同状态
                            Integer v_ = good.get(k); //当前状态物品的价格
                            Integer w_ = weight.get(k);//当前状态物品的满意度
                            if ( j >= v_){
                                max = Math.max(Math.max(dp[j - v_] + w_,dp[j]),max);
                            }
                        }
                        dp[j] = max; //当前money = j时，能获得的最大满意度是max
                    }
                }
            }

这题花的时间挺久的，必须写个题解记录，防止遗忘