题解 HJ16 | #购物单#

import java.util.Scanner;

// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        //接收输入
        int money=in.nextInt();
        int num=in.nextInt();
        int[][] things=new int[num][3];
        for(int i=0,j=0;i<num;i++){
            things[i][j]=in.nextInt();j++;
            things[i][j]=in.nextInt();j++;
            things[i][j]=in.nextInt();j=0;
        }
        /*for(int i=0,j=0;i<5;i++){
        System.out.print(things[i][j]);j++;
        System.out.print(things[i][j]);j++;
        System.out.println(things[i][j]);j=0;
        }*/
        //建立一个总份数表，比如一个带有2个附件的主件，有四种可能，分别是0+1，0+2，0，0+1+2，带一个附件就是0，0+1，不带附件就是0
        //为此要先算出对应的可能数，建立一个新表
        int count=0;
        for(int i=0;i<num;i++){
            if (things[i][2]==0){
                count++;
                int j=0;
                for(;j<num;j++){
                    if(things[j][2]==i+1){
                        count++;break;
                    }                
                }
                for(;j<num;j++){
                    if(things[j][2]==i+1){
                        count+=2;break;
                    }                
                }
            }
        }//计算新表长度
        //System.out.print(count);
        int[][] list=new int[count][3];
        count=0;
        for(int i=0;i<num;i++){
            if (things[i][2]==0){
                list[count][0]=things[i][0];//价格
                list[count][1]=things[i][0]*things[i][1];//满意度
                list[count][2]=1;
                count++;
                int j=0;
                for(;j<num;j++){
                    if(things[j][2]==i+1){
                        list[count][0]=things[j][0]+things[i][0];//价格
                        list[count][1]=things[j][0]*things[j][1]+things[i][0]*things[i][1];//满意度
                        list[count-1][2]=2;
                        count++;   
                        j++;                     
                        break;
                    }                
                }
                for(;j<num;j++){
                    if(things[j][2]==i+1){
                        list[count][0]=things[j][0]+list[count-2][0];//价格
                        list[count][1]=things[j][0]*things[j][1]+list[count-2][1];//满意度
                        list[count-2][2]=4;
                        count++;      
                        list[count][0]=things[j][0]+list[count-2][0];//价格
                        list[count][1]=things[j][0]*things[j][1]+list[count-2][1];//满意度            
                        count++;
                        break;
                    }                
                }
            }
        }
        int[] val=new int[money/10+1];
        for(int i=0;i<count;i++){
            if(list[i][2]!=0){
                if(list[i][2]==1){
                for(int j=money/10;j>=list[i][0]/10;j--)
                val[j]=Math.max(val[j],val[j-list[i][0]/10]+list[i][1]);
                }
                else if(list[i][2]==2){
                    int j=money/10;
                    for(;j>=list[i+1][0]/10;j--)
                        val[j]=Math.max(Math.max(val[j],val[j-list[i][0]/10]+list[i][1]),val[j-list[i+1][0]/10]+list[i+1][1]);
                    for(;j>=list[i][0]/10;j--)
                        val[j]=Math.max(val[j],val[j-list[i][0]/10]+list[i][1]);
                }
                else if(list[i][2]==4){
                    int j=money/10;
                    for(;j>=list[i+3][0]/10;j--)
                        val[j]=Math.max(Math.max(Math.max(Math.max(val[j],val[j-list[i][0]/10]+list[i][1]),val[j-list[i+1][0]/10]+list[i+1][1]),val[j-list[i+2][0]/10]+list[i+2][1]),val[j-list[i+3][0]/10]+list[i+3][1]);
                    if(list[i+1][0]>=list[i+2][0]){
                        for(;j>=list[i+1][0]/10;j--)
                            val[j]=Math.max(Math.max(Math.max(val[j],val[j-list[i][0]/10]+list[i][1]),val[j-list[i+1][0]/10]+list[i+1][1]),val[j-list[i+2][0]/10]+list[i+2][1]);
                        for(;j>=list[i+2][0]/10;j--)
                            val[j]=Math.max(Math.max(val[j],val[j-list[i][0]/10]+list[i][1]),val[j-list[i+2][0]/10]+list[i+2][1]);
                    }
                    else{
                        for(;j>=list[i+2][0]/10;j--)
                            val[j]=Math.max(Math.max(Math.max(val[j],val[j-list[i][0]/10]+list[i][1]),val[j-list[i+1][0]/10]+list[i+1][1]),val[j-list[i+2][0]/10]+list[i+2][1]);
                        for(;j>=list[i+1][0]/10;j--)
                            val[j]=Math.max(Math.max(val[j],val[j-list[i][0]/10]+list[i][1]),val[j-list[i+1][0]/10]+list[i+1][1]);
                }
                    for(;j>list[i][0]/10;j--)
                        val[j]=Math.max(val[j],val[j-list[i][0]/10]+list[i][1]);
                }
            }
        }
        System.out.print(val[money/10]);

    }
}

思路是动态规划，01背包问题，但是这个相比于正常的01背包问题又多了个主附件问题

可以按照主键进行分类

一个主键有一种，一个主键带一个附件有，主，主+附俩种，而一个主键+俩个附件有 主，主+附1，主+附2，主+附1+附2，四种

我先算出有多少种可能

    //建立一个总份数表，比如一个带有2个附件的主件，有四种可能，分别是0+1，0+2，0，0+1+2，带一个附件就是0，0+1，不带附件就是0
    //为此要先算出对应的可能数，建立一个新表
    int count=0;
    for(int i=0;i<num;i++){
        if (things[i][2]==0){
            count++;
            int j=0;
            for(;j<num;j++){
                if(things[j][2]==i+1){
                    count++;break;
                }                
            }
            for(;j<num;j++){
                if(things[j][2]==i+1){
                    count+=2;break;
                }                
            }
        }
    }//计算新表长度

之后我建立了一个新表，这个表长度为之前算的可能性，宽度为3，第一个放重量，第二个放满意度，第三个放这个是哪一种

如果是单主则为1，如果是主+1附为2，如果是主+2附则为4

比如为4的

第i行放主的重量和满意度

第i+1行放主+1附的重量和满意度

第i+2行放主+2附的重量和满意度

第i+3行放主+1+2附的重量和满意度

int[][] list=new int[count][3];

count=0;

for(int i=0;i<num;i++){

if (things[i][2]==0){

list[count][0]=things[i][0];//价格

list[count][1]=things[i][0]*things[i][1];//满意度

list[count][2]=1;

count++;

int j=0;

for(;j<num;j++){

if(things[j][2]==i+1){

list[count][0]=things[j][0]+things[i][0];//价格

list[count][1]=things[j][0]*things[j][1]+things[i][0]*things[i][1];//满意度

list[count-1][2]=2;

count++;

j++;

break;

}

}

for(;j<num;j++){

if(things[j][2]==i+1){

list[count][0]=things[j][0]+list[count-2][0];//价格

list[count][1]=things[j][0]*things[j][1]+list[count-2][1];//满意度

list[count-2][2]=4;

count++;

list[count][0]=things[j][0]+list[count-2][0];//价格

list[count][1]=things[j][0]*things[j][1]+list[count-2][1];//满意度

count++;

break;

}

}

}

}

之后创建一个动态规划表 int[] val=new int[money/10+1];长度为money/10这个表初始全为0

遇到单主，大于这个主的重量的部分，遍历一遍，val[j]的值在表原本的值和val[j-list[i][0]/10]+list[i][1]取最大的那个

，j表示的是重量，val[j-list[i][0]/10]的意思是减去这个件的满意度最大值，再加上这个件的满意度

if(list[i][2]==1){

for(int j=money/10;j>=list[i][0]/10;j--)

val[j]=Math.max(val[j],val[j-list[i][0]/10]+list[i][1]);

}

后面遇到主+1附，在大于主+附重量时，从val[j] 原最大满意度,val[j-list[i][0]/10]+list[i][1]) 减去主重量的最大满意度+主的满意度,val[j-list[i+1][0]/10]+list[i+1][1] 减去主+附的重量最大满意+主+附的满意度中选择最大的

在小于主+附，又大于主，则和之前一样

else if(list[i][2]==2){

int j=money/10;

for(;j>=list[i+1][0]/10;j--)

val[j]=Math.max(Math.max(val[j],val[j-list[i][0]/10]+list[i][1]),val[j-list[i+1][0]/10]+list[i+1][1]);

for(;j>=list[i][0]/10;j--)

val[j]=Math.max(val[j],val[j-list[i][0]/10]+list[i][1]);

}

主+2附，又分为大于主+2附，大于主+附件重的那个，大于主+附件轻的那个，大于主四种

else if(list[i][2]==4){

int j=money/10;

for(;j>=list[i+3][0]/10;j--)

val[j]=Math.max(Math.max(Math.max(Math.max(val[j],val[j-list[i][0]/10]+list[i][1]),val[j-list[i+1][0]/10]+list[i+1][1]),val[j-list[i+2][0]/10]+list[i+2][1]),val[j-list[i+3][0]/10]+list[i+3][1]);

if(list[i+1][0]>=list[i+2][0]){

for(;j>=list[i+1][0]/10;j--)

val[j]=Math.max(Math.max(Math.max(val[j],val[j-list[i][0]/10]+list[i][1]),val[j-list[i+1][0]/10]+list[i+1][1]),val[j-list[i+2][0]/10]+list[i+2][1]);

for(;j>=list[i+2][0]/10;j--)

val[j]=Math.max(Math.max(val[j],val[j-list[i][0]/10]+list[i][1]),val[j-list[i+2][0]/10]+list[i+2][1]);

}

else{

for(;j>=list[i+2][0]/10;j--)

val[j]=Math.max(Math.max(Math.max(val[j],val[j-list[i][0]/10]+list[i][1]),val[j-list[i+1][0]/10]+list[i+1][1]),val[j-list[i+2][0]/10]+list[i+2][1]);

for(;j>=list[i+1][0]/10;j--)

val[j]=Math.max(Math.max(val[j],val[j-list[i][0]/10]+list[i][1]),val[j-list[i+1][0]/10]+list[i+1][1]);

}

for(;j>list[i][0]/10;j--)

val[j]=Math.max(val[j],val[j-list[i][0]/10]+list[i][1]);

}

}

最后输出最大的满意度：System.out.print(val[money/10]);