题解 | #购物单#

购物单

http://www.nowcoder.com/practice/f9c6f980eeec43ef85be20755ddbeaf4

首先，给定的物品之间存在从属关系，所以如果把附件不单独看成物品而归类开主件中的话，那么主件的价格和重要度就可能各存在4种情况（光主件，主件加附件1，主件加附件2，主件加附件1和2）。

我们把主件及及可选附件算成一件完成的物品(class good)，存在4个price变量和4个value变量(value=price 乘重要度) main函数中除最后一行外就是在构建一个good数组（gds数组，元素个数为主件数）。

最后关于给定的物品在给定的金钱限定下得到的价值最优解，由getMaxValue(good[] gds,int money)实现。

这个问题本质上是0-1背包问题（背包容量即为金钱限额）。网上有很多关于它的笔记，我这里说下我认为的最通俗的理解方法。

这里构建一个二维数组tmp[][],第一个维度代表物品维度，第二个维度代表金钱维度。

其实物品维度中，各个物品的排序顺序随意确定即可，这里就按输入顺序来就行。

为理解方便，tmp[0][j]表示一个物品都没有的情况下，背包容量为j时，可装下的最大价值，很显然应该为0；

同理，tmp[i][0]表示背包容量为0的情况下，存在i个物品可供挑选时，可装下的最大价值，很明显也应该为0；

tmp[i][j]表示：在前i个物品可选，且背包容量为j时，可装下的最大价值。

其取值逻辑为：

1.如果第i个物品的4个价值有<=背包容量j的，那就需要尝试着将它放入背包，看看是否比不放入的时候价值大。

2.如果不放入，则tmp[i][j]=tmp[i-1][j],就是说跟没见到第i个物品，背包容量为j时记录的最大价值一样

3.如果放入，则要考虑放哪一种组合。

假定该物品某个价格为price,价值为value，如果要放入这个物品，最起码要让当前容量为j的背包空出price的空间，因此，我们可以用 tmp[i-1][j-price]的值+value来求得放入后的总价值，其中tmp[i-1][j-price]表示前i-1个物品出现，且背包容量为j-price的最大容量。

4.4种价格依次尝试后的4个价值外加不放入时tmp[i-1][j]，这5个值中求最大值，即为tmp[i][j]的最大值，记录到数组元素中

5.tmp[主件数][最大金钱数]即为我要的最终解。

代码如下：

import java.util.*;

public class Main {
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        int money = sc.nextInt();
        int count = sc.nextInt();
        HashMap<Integer,Integer> fjPrice=new HashMap<Integer,Integer>();
        HashMap<Integer,Integer> fjValue=new HashMap<Integer,Integer>();
        good[] gds = new good[count];
        for(int i = 0; i < count; i++){
            int price = sc.nextInt();
            int value = price*sc.nextInt();
            int belong = sc.nextInt();
            if(belong == 0){//如果是主件，第几个进来就放到对应下标i的元素中
                if(gds[i]!=null) {//如果对象已经存在，把主件的信息录入进去，否则直接以附件信息生成对象
                    gds[i].setMainV_P(price,value);
                }else{
                    gds[i] = new good(price, value, 1);
                }
            }else{//否则记录到belong-1下标的元素中
                if(gds[belong-1]!=null){//如果对象已经存在，把附件的信息录入进去，否则直接以附件信息生成对象
                    gds[belong-1].setAllV_P(price,value);
                }else{
                    gds[belong-1]=new good(price,value,0);
                }
            }
        }
        ArrayList<good> agds = new ArrayList<good>();
        for(good gd:gds){
            if(gd != null){
                agds.add(gd);
            }
        }
        gds = new good[agds.size()];
        for(int i=0;i<agds.size();i++){
            gds[i]=agds.get(i);
        }
        System.out.println(getMaxValue(gds,money));
    }
    public static int getMaxValue(good[] gds,int money){
        int[][] tmp = new int[gds.length+1][money+1];
        for(int i = 0;i<=gds.length;i++){
            tmp[i][0]=0;
        }
        for(int j=0;j<=money;j++){
            tmp[0][j]=0;
        }
        for(int i = 1;i<=gds.length;i++){
            for(int j=1;j<=money;j++){//判断每个tmp[i][j]的最大值
                //如果gds[i]的4个价格有存在<=j的情况，才会考虑要不要把这个物品放入背包
                int value0=0;
                int valueWith1=0;
                int valueWith2=0;
                int valueWithAll=0;
                if(gds[i-1].price0<=j){
                    value0 = tmp[i-1][j-gds[i-1].price0]+gds[i-1].value0;
                }
                if(gds[i-1].priceWith1<=j){
                    valueWith1 = tmp[i-1][j-gds[i-1].priceWith1]+gds[i-1].valueWith1;
                }
                if(gds[i-1].priceWith2<=j){
                    valueWith2 = tmp[i-1][j-gds[i-1].priceWith2]+gds[i-1].valueWith2;
                }
                if(gds[i-1].priceWithAll<=j){
                    valueWithAll = tmp[i-1][j-gds[i-1].priceWithAll]+gds[i-1].valueWithAll;
                }
                tmp[i][j]=Math.max(Math.max(Math.max(Math.max(tmp[i-1][j],value0),valueWith1),valueWith2),valueWithAll);
                //System.out.print(tmp[i][j]+" ");
            }
            //System.out.println();
        }
        return tmp[gds.length][money];
    }
    public static class good{
        public int price0=0;
        public int priceWith1=0;
        public int priceWith2=0;
        public int priceWithAll=0;
        public int value0=0;
        public int valueWith1=0;
        public int valueWith2=0;
        public int valueWithAll=0;
        public good(int price,int value,int flag){
            if(flag ==1) {//flag=1表示以主件信息构建物品
                this.price0 = price;
                this.priceWith1 = price;
                this.priceWith2 = price;
                this.priceWithAll = price;
                this.value0 = value;
                this.valueWith1 = value;
                this.valueWith2 = value;
                this.valueWithAll = value;
            }else{
                setAllV_P(price,value);
            }
        }
        public void setAllV_P(int price,int value){
            if(valueWith1==value0){//第一个附件进来的时候设置valueWith1和valueWithAll,priceWith1和priceWithAll
                valueWith1+=value;
                valueWithAll+=value;
                priceWith1+=price;
                priceWithAll+=price;
            }else if(valueWith2==value0){//第二个附件进来时，设置valueWith2和valueWithAll,priceWith2和priceWithAll
                valueWith2+=value;
                valueWithAll+=value;
                priceWith2+=price;
                priceWithAll+=price;
            }
        }
        public void setMainV_P(int price,int value){
            this.price0 += price;
            this.priceWith1 += price;
            this.priceWith2 += price;
            this.priceWithAll += price;
            this.value0 += value;
            this.valueWith1 += value;
            this.valueWith2 += value;
            this.valueWithAll += value;
        }
    }
}