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]);
京公网安备 11010502036488号