[数据结构与算法]牛客-HJ16-购物单

题目

思路

1. 和背包问题的区别在于有无主附件
2. 于是考虑每个物品时要考虑每种可能出现的情况，1、主件，2、主件+附件1，3、主件+附件2，4、主件+附件1+附件2
   可以看出一个商品（如果是主件的话）一共有四种情况 如果是附件的话就和普通一样

代码

import java.util.Vector;
import java.util.Scanner;
public class Main {
    public static <StringBuiler> void main(String[] args) {
        //记录运算符
        Scanner s = new Scanner(System.in);
        //总钱数
        int N = s.nextInt();
        //除个10 方便构建计算
        N=N/10;
        //希望购买的物品的总数
        int m = s.nextInt();
        //四种情况:1.主件 2.主件+附件1 3.主件+附件2 4.主件+附件1+附件2
        //为了将主附件连接起来 所以数组大小设置为3
        //用price存储各商品的价格数组 以allprice用来存储各商品的乘值
        int[][] price = new int[m][3];
        int[][] allprice = new int[m][3];
        //开始读取
        for(int i=0;i<m;i++){
            int a = s.nextInt()/10;
            int b = s.nextInt();
            int c = s.nextInt();
            //如果是主件的话
            if(c==0){
                price[i][0]=a;
                allprice[i][0]=a*b;
            }//如果是附件的话
            else{
                //判断是不是第二个附件 由于编号问题 所以c需要-1
                if(price[c-1][1]==0){
                    price[c-1][1] = a;
                    allprice[c-1][1] = a*b;
                }else{
                    price[c-1][2] = a;
                    allprice[c-1][2] = a*b;
                }
            }
        }
        //开始使用分组背包 创建dp背包 行为商品+1 列为总钱数+1
        int[][] dp = new int[m+1][N+1];
        //dp[i][j]的概念为从前i个主件中选取，奖金数量为j的情况下，所获得的最大价格*重要程度累加和
        //可知dp[0][i]=0 dp[i][0]也必为0 所以从1开始算
        for(int i=1;i<=m;++i){
            for(int j=1;j<=N;++j){
                //开始获取这个商品及其顺带的所有消息 如果它是附件的话其它为0 不影响
                int a = price[i-1][0], b = allprice[i-1][0]; //主1
                int c = price[i-1][1], d = allprice[i-1][1]; //辅1
                int e = price[i-1][2], f = allprice[i-1][2]; //辅2
                //开始进行连续的dp判断 如果可以把a塞进去的话
                dp[i][j] = j >= a ? Math.max(dp[i-1][j-a] + b, dp[i-1][j]) : dp[i-1][j];
                //如果可以把ab塞进去的话
                dp[i][j] = j>=(a+c) ? Math.max(dp[i-1][j-a-c]+b+d,dp[i][j]) : dp[i][j];
                dp[i][j] = j >= (a+e) ? Math.max(dp[i-1][j-a-e] + b + f, dp[i][j]) : dp[i][j];
                dp[i][j] = j >= (a+c+e) ? Math.max(dp[i-1][j-a-c-e] + b + d + f, dp[i][j]) : dp[i][j];
            }
        }
        System.out.print(dp[m][N] * 10);
        return ;
    }
}