/*
测试这个例子时，可以让
N = N/100;//总金额/100
int v = Integer.parseInt(s[0])/100;//单价/100。
方便看数字替换规律。
1500 7
500 1 0
400 4 0
300 5 1
400 5 1
200 5 0
500 4 0
400 4 0
MDNumber:5
prices0 prices0 prices0
prices50 prices30 prices40
prices40 prices0 prices0
prices0 prices0 prices0
prices0 prices0 prices0
prices20 prices0 prices0
prices50 prices0 prices0
prices40 prices0 prices0
weights0 weights0 weights0
weights50 weights150 weights200
weights160 weights0 weights0
weights0 weights0 weights0
weights0 weights0 weights0
weights100 weights0 weights0
weights200 weights0 weights0
weights160 weights0 weights0
* */
/*
if( q!=0 && prices[q][1]!=0 && prices[q][2]==0){//说明是附件2
prices[q][2] = v;//单价/10。
weights[q][2] = v * p;//满意度= 单价/10 * 重要度。
}
//注意！！！！！！！！！！！注意！！！！！
//先判断附件一有没有，没有就写附件二。但是不能先写附件1，不然附件二本来就是0，附件一也被填写了。就会把附件一再次写到附件二中。
if( q!=0 && prices[q][1]==0 ){//说明是附件1
prices[q][1] = v;//单价/10。
weights[q][1] = v * p;//满意度= 单价/10 * 重要度。
}
例如这个例子。
4500 12
100 3 0
400 5 0
300 5 0
1400 2 0
500 2 0
800 2 4
1400 5 4
300 5 0
1400 3 8
500 2 0
1800 4 0
440 5 10
* */
import java.util.Scanner;
import static java.lang.Math.max;
// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int N = sc.nextInt();//N （ N<32000 ）表示总钱数
int m = sc.nextInt();// m （m <60 ）为可购买的物品的个数
sc.nextLine();
int[][] prices = new int[m+1][3]; //存放主件价格 附件1价格 附件2价格
int[][] weights = new int[m+1][3]; //存放主件满意度 附件1满意度 附件2满意度
N = N/10;//为了减少运算，把单价格统一除以10。总钱数也除以10。
int MDNumber = 0;//记录主件个数
for (int i = 1; i < m+1; i++) {
String str = sc.nextLine();
String s[] = str.split(" ");
int v = Integer.parseInt(s[0])/10;//单价/10。
int p = Integer.parseInt(s[1]);
int q = Integer.parseInt(s[2]);
if(q==0){//说明是主件
prices[i][0] = v;//单价/10。
weights[i][0] = v * p;//满意度= 单价/10 * 重要度。
MDNumber++;
}
if( q!=0 && prices[q][1]!=0 && prices[q][2]==0){//说明是附件2
prices[q][2] = v;//单价/10。
weights[q][2] = v * p;//满意度= 单价/10 * 重要度。
}
//注意！！！！！！！！！！！注意！！！！！
//先判断附件一有没有，没有就写附件二。但是不能先写附件1，不然附件二本来就是0，附件一也被填写了。就会把附件一再次写到附件二中。
if( q!=0 && prices[q][1]==0 ){//说明是附件1
prices[q][1] = v;//单价/10。
weights[q][1] = v * p;//满意度= 单价/10 * 重要度。
}
}
/*
System.out.println("MDNumber:" + MDNumber);
System.out.println();
for (int i = 0; i < m+1; i++) {
for (int j = 0; j < 3; j++) {
System.out.print("prices" + prices[i][j]+" ");
}
System.out.println();
}
System.out.println();
for (int i = 0; i < m+1; i++) {
for (int j = 0; j < 3; j++) {
System.out.print("weights" + weights[i][j]+" ");
}
System.out.println();
}
*/
/* 计算：主件：MD 、附件1：AO、附件2：AT、附件1+附件2：AOT
主件、主件+附件1、主件+附件2、主件+附件1+附件2
不超过最大金额N，且每个主件的这四种情况的混合相加的最大满意度。
*/
int[][] f = new int[m+1][N+1];//每一个物件（m个主件）都可以搭配其他的附件或者主件去凑齐N元钱。
for (int i = 1; i < m+1; i++) {//每一个物件（m个主件）
for (int j = 0; j < N+1; j++) {//只要花费不超过N元即可
int p0 = prices[i][0];//主件价格
int p1 = prices[i][1];//附件1价格
int p2 = prices[i][2];//附件2价格
int w0 = weights[i][0];//主件满意度
int w1 = weights[i][1];//附件1满意度
int w2 = weights[i][2];//附件2满意度
/*
f[i-1][j]表示没有加这个主件之前，在j元时，买前i-1个物品可以得到的最大满意度
f[i][j]表示在j元时，买前i个物品可以得到的最大满意度
f[i-1][j-p0]+w0表示在j元时，买前i-1个物品，又消费p0元之后，买了第i个物品，可以得到的最大满意度+w0，是不是总体最大满意度，不能确定。
f[i-1][j-p0-p1]+w0+w1表表示在j元时，买前i-1个物品，又消费p0+p1元之后，可以得到的最大满意度+w0+w1，是不是总体最大满意度，不能确定。
f[i-1][j-p0-p2]+w0+w2表示在j元时，买前i-1个物品，又消费p0+p2元之后，可以得到的最大满意度+w0+w2，是不是总体最大满意度，不能确定。
f[i-1][j-p0-p1-p2]+w0+w1+w2表示在j元时，买前i-1个物品，又消费p0+p1+p2元之后，可以得到的最大满意度+w0+w1+w2，是不是总体最大满意度，不能确定。
* */
/*总结：就是把主件看做是数组的每一行，N元钱代表数组的列数。
列数是固定的钱数，但是每一行的每一列的值代表在j列的时候，每次加减主件或者附件之后的【最大满意度】。
把i-1行的【(j元钱-p0)元钱时的最大满意度】+w0 = 购买p0之后 j元钱时的【最大满意度】
和
i-1行的（j元钱）不购买p0时 j元钱时的【最大满意度】
进行最大满意度的比较，
得到 下一行
第i行的j元【最大满意度】。
从前面的比较中得到j元的【最大满意度】，但是【并不是一定是购买了此商品】。
最后一行得到的是每一个j元时的最大满意度的一组数。
* */
//主件：MD
f[i][j] = p0 <= j ? Math.max(f[i-1][j-p0]+w0,f[i-1][j]) : f[i-1][j];
//在j元时，买了前i-1个物品，p0<=j,还可以再买第i个物品。把 买第i个物品之后的满意度 和 买第i-1个物品的最大满意度 比大小，得出j元内最大满意度。p0>j,不能再买第i个物品，就让j元时，只买第i-1个物品。
//主件+附件1
f[i][j] = p0 + p1 <= j ? Math.max(f[i-1][j-p0-p1]+w0+w1,f[i][j]) : f[i][j];
//主件+附件2
f[i][j] = p0 + p2 <= j ? Math.max(f[i-1][j-p0-p2]+w0+w2,f[i][j]) : f[i][j];
//主件+附件1+附件2
f[i][j] = p0 + p1 + p2 <= j ? Math.max(f[i-1][j-p0-p1-p2]+w0+w1+w2,f[i][j]) : f[i][j];
}
}
System.out.println(f[m][N]*10);
}
}
京公网安备 11010502036488号