购物单

import java.util.*;
/*
有依赖的背包问题
附件依赖于主件，其实还是选主件的问题，只是在不选和怎么选之间选择
设dp[i][j]表示前i件物品成本不超过j元时获得的最大满意度
只针对主件，x表示上一个主件的位置,遇到附件之间跳过
1)不选当前主件:dp[i][j]=dp[x][j]
2)只选主件:dp[i][j]=Math.max(第一种情况,dp[x][j-主件价格]+主件满意度)
3)选主件+附件1:dp[i][j]=Math.max(前两种情况,dp[x][j-主件价格-附件1价格]+主件满意度+附件1满意度)
4)选主件+附件2:dp[i][j]=Math.max(前三种情况,dp[x][j-主件价格-附件2价格]+主件满意度+附件2满意度)
5)选主件+附件1+附件2:dp[i][j]=Math.max(前四种情况,dp[x][j-主件价格-附件1价格-附件2价格]+主件满意度+附件1满意度+附件2满意度)
需要二维数组follows[][]存储主件对应的附件位置,方便在操作当前主件时能够找到对应的附件
 */
// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        //输入总预算、物品个数
        int n=in.nextInt();
        int m=in.nextInt();
        //输入各个物品的价格、重要度、编号
        int []costs=new int [m];
        int []value=new int [m];
        int []points=new int [m];
        for(int i=0;i<m;i++){
            costs[i]=in.nextInt();
            value[i]=costs[i]*in.nextInt();//直接计算满意度
            points[i]=in.nextInt();
        }
        //follows记录主件的附件位置，初始化为-1
        int [][]follows=new int [m][2];//最多只有两个附件
        for(int []row:follows) Arrays.fill(row,-1); 
        for(int i=0;i<m;i++)
            if(points[i]!=0){
                //先判断第几个附件
                //如果是第一个
                if(follows[points[i]-1][0]==-1) follows[points[i]-1][0]=i;
                else follows[points[i]-1][1]=i;
            }
        //开始背包
        int [][]dp = new int [m+1][n+1];
        dp[0][0]=0;
        int x=0;
        for(int i=1;i<=m;i++){
            //不是主件直接跳过
            if(points[i-1]!=0) continue;
            for(int j=0;j<=n;j++){
                //第一种情况，不选当前主件
                dp[i][j]=dp[x][j];
                //第二种情况，只选主件
                if(j>=costs[i-1])
                    dp[i][j]=Math.max(dp[i][j],dp[x][j-costs[i-1]]+value[i-1]);//与第一种情况比较
                //第三种情况，选主件+附件1(如果有的话)
                if(follows[i-1][0]!=-1 && j>=costs[i-1]+costs[follows[i-1][0]])
                    dp[i][j]=Math.max(dp[i][j],dp[x][j-costs[i-1]-costs[follows[i-1][0]]]+value[i-1]+value[follows[i-1][0]]);//与第二种情况比较
                //第四种情况，选主件+附件2(如果满足条件)
                if(follows[i-1][1]!=-1 && j>=costs[i-1]+costs[follows[i-1][1]])
                    dp[i][j]=Math.max(dp[i][j],dp[x][j-costs[i-1]-costs[follows[i-1][1]]]+value[i-1]+value[follows[i-1][1]]);//与第三种情况比较
                //第五种情况，选主件+附件1+附件2
                if(follows[i-1][0]!=-1 && follows[i-1][1]!=-1 && j>=costs[i-1]+costs[follows[i-1][0]]+costs[follows[i-1][1]])
                    dp[i][j]=Math.max(dp[i][j],dp[x][j-costs[i-1]-costs[follows[i-1][0]]-costs[follows[i-1][1]]]+value[i-1]+value[follows[i-1][0]]+value[follows[i-1][1]]);
            }
            //当前的主件换成上一次的主件
            x=i;
        }
        //最后输出最后一个主件的位置
        System.out.print(dp[x][n]);
    }
}

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int budget=in.nextInt();
        int n=in.nextInt();
        if(n<=0||budget<=0){
            System.out.println(0);
        }
        good[] g=new good[n+1];
        for(int i=1;i<=n;i++){
            int v=in.nextInt();
            int w=in.nextInt();
            int q=in.nextInt();
            if(g[i]!=null){ //如果g[i] 对象已创建，则只需赋值，否则要实例化
                g[i].setvwq(v,w,q);
            }else{
                g[i]=new good(v,w,q);
            }
            if(g[i].q>0){
                //附件的主件对象未实例化时，先实例化
                if(g[q]==null){
                    g[q]=new good(0,0,0);
                }
                g[q].setGood(g[i]);
            }
        }
        int dp[][]=new int[n+1][budget/10 +1];
        for(int i=1;i<=n;i++){
            int v=0,v1=0,v2=0,v3=0,sa=0,sa1=0,sa2=0,sa3=0;
            //只有主件(下一个循环语句中过滤掉附件)
            v=g[i].v;
            sa=g[i].v*g[i].w;
            //主件+附件1
            if(g[i].good1!=null){
                v1=v+g[i].good1.v;
                sa1=sa+g[i].good1.v*g[i].good1.w;
            }
            if(g[i].good2!=null){
                //主件+附件2
                v2=v+g[i].good2.v;
                sa2=sa+g[i].good2.v*g[i].good2.w;
                //主件+附件1+附件2
                v3=v+g[i].good1.v+g[i].good2.v;
                sa3=sa+g[i].good1.v*g[i].good1.w+g[i].good2.v*g[i].good2.w;
            }
            for(int j=1;j<=budget/10;j++){
                if(g[i].q>0){  //附件跳过
                    dp[i][j]=dp[i-1][j];
                }else{
                    dp[i][j]=dp[i-1][j];
                    if(j>=v/10&&v!=0) dp[i][j]=Math.max(dp[i][j],dp[i-1][j-v/10]+sa);
                    if(j>=v1/10&&v1!=0) dp[i][j]=Math.max(dp[i][j],dp[i-1][j-v1/10]+sa1);
                    if(j>=v2/10&&v2!=0) dp[i][j]=Math.max(dp[i][j],dp[i-1][j-v2/10]+sa2);
                    if(j>=v3/10&&v3!=0) dp[i][j]=Math.max(dp[i][j],dp[i-1][j-v3/10]+sa3);
                }
            }
        }
        System.out.println(dp[n][budget/10]);
    }
    public static class good{
        int v;
        int w;
        int q;

        good good1;
        good good2;
        public good(int v,int w,int q){
            this.v=v;
            this.w=w;
            this.q=q;
        }
        public void setvwq(int v,int w,int q){
            this.v=v;
            this.w=w;
            this.q=q;
        }
        public void setGood(good goodChild){
            if(this.good1==null){
                this.good1=goodChild;
            }else if(this.good2==null){
                this.good2=goodChild;
            }
        }
    } 
}

package org.example;
import java.util.*;

// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Shopping {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        // 注意 hasNext 和 hasNextLine 的区别
        int yuSuan = in.nextInt();
        int goodsNum = in.nextInt();
        int[][] goodsArr = new int[goodsNum][3];
        for (int i = 0; i < goodsNum; i++) {
            goodsArr[i][0] = in.nextInt();
            goodsArr[i][1] = in.nextInt();
            goodsArr[i][2] = in.nextInt();
        }

        //为每个主件维护一个链表，代表其不同的价值选项
        ArrayList<HashMap<Integer, Integer>> mainGoodsMapList = new
                ArrayList<HashMap<Integer, Integer>>();
        for (int i = 0; i < goodsArr.length; i++) {

            if (goodsArr[i][2] == 0) {
                HashMap<Integer, Integer> valueMap = new HashMap<>();
                valueMap.put(goodsArr[i][0], goodsArr[i][0] * goodsArr[i][1]);
                int maxValue = goodsArr[i][0]  ;
                int maxSatisfaction = goodsArr[i][0] * goodsArr[i][1];
                int fujianNum = 0;
                for (int j = 0; j < goodsArr.length; j++) {
                    if (goodsArr[j][2] - 1 == i) {
                        fujianNum++;
                        maxValue += goodsArr[j][0];
                        maxSatisfaction += goodsArr[j][0] * goodsArr[j][1];
                        valueMap.put(goodsArr[i][0] + goodsArr[j][0],
                                goodsArr[i][0] * goodsArr[i][1] + goodsArr[j][0] * goodsArr[j][1]);
                        if (fujianNum == 2) {

                            valueMap.put(maxValue, maxSatisfaction);
                        }
                    }
                }
                mainGoodsMapList.add(valueMap) ;
            }

        }

        int result = getMaxSatisfaction(mainGoodsMapList.size() - 1, mainGoodsMapList,
                yuSuan);
        System.out.println(result);
    }
    public static int getMaxSatisfaction(int newMainGoodsIndex, ArrayList<HashMap<Integer, Integer>> mainGoodsMapList , int yuSuan){
        HashMap<Integer, Integer> newMainGoodsMap = mainGoodsMapList.get(newMainGoodsIndex);

        if(newMainGoodsIndex == 0){
            if(yuSuan <= 0){
                return 0;
            }
            int result = 0;
            int temp = 0;
            for(int item:newMainGoodsMap.keySet()){
                if(item <= yuSuan && newMainGoodsMap.get(item) > temp){
                    result = newMainGoodsMap.get(item);
                }
            }
            return result;
        }
        else {
            int lastMaxSatisfaction = getMaxSatisfaction(newMainGoodsIndex-1, mainGoodsMapList, yuSuan);
            int currentMaxSatisfaction = lastMaxSatisfaction;
            for(int item:newMainGoodsMap.keySet()){
                if(item <= yuSuan){
                    currentMaxSatisfaction = Math.max(currentMaxSatisfaction, newMainGoodsMap.get(item) +
                            getMaxSatisfaction(newMainGoodsIndex-1, mainGoodsMapList, yuSuan-item)
                    );
                }
            }
            return currentMaxSatisfaction;
        }
    }
}

import java.util.ArrayList;
import java.util.Scanner;

/**
 * Description:
 * Author: fy
 * Date: 2024/11/14 7:21
 */

public class Main {

    static class Products {
        int price;
        int important;
        int index;

        public Products(int price, int important, int index) {
            this.price = price;
            this.important = important;
            this.index = index;

        }

        @Override
        public String toString() {
            return "价格：" + price + " 重要度：" + important + " 索引：" + index;
        }
    }

    public static void main(String[] args) {

        Scanner in = new Scanner(System.in);
        String s = in.nextLine();
        String[] split = s.split(" ");
        int amount = Integer.parseInt(split[0]);
        int productCount = Integer.parseInt(split[1]);


        ArrayList<Products> mainList = new ArrayList<>();
        ArrayList<ArrayList<Products>> attachList = new ArrayList<>();
        for (int i = 0; i < productCount; i++) {
            attachList.add(new ArrayList<>());

        }
        int record = 0;
        for (int i = 0; i < productCount; i++) {
            String proStr = in.nextLine();
            String[] proSplit = proStr.split(" ");
            int price = Integer.parseInt(proSplit[0]);
            int important = Integer.parseInt(proSplit[1]);
            int mainProductIndex = Integer.parseInt(proSplit[2]);
            int index = record;

            if (mainProductIndex == 0) {
                //存主件
                Products products = new Products(price, important, index);
                mainList.add(products);
            } else {
                //存附件
                if (attachList.get(mainProductIndex - 1) == null) {
                    attachList.set(mainProductIndex - 1, new ArrayList<>());
                }
                Products products = new Products(price, important, index);
                attachList.get(mainProductIndex - 1).add(products);
            }
            record++;
        }

        int[] dp = new int[amount + 1];
        dp[0] = 0;

        for (int i = 0; i < mainList.size(); i++) {
            Products products = mainList.get(i);
            int price = products.price;
            int important = products.important;
            int index = products.index;

            for (int j = amount; j > 0; j--) {
                //如果为空只考虑加或不加主件
                if (attachList.get(index).isEmpty()) {
                    if (j >= price) {
                        dp[j] = Math.max(dp[j], dp[j - price] + important * price);
                    }
                } else {
                    //如果有附件 先看看存不存主件
                    if (j >= price) {
                        dp[j] = Math.max(dp[j], dp[j - price] + important * price);
                    }
                    //在分别考虑 主件+附件1 和 主件+附件2  要不要为dp[j构成满意度
                    for (int k = 0; k < attachList.get(index).size(); k++) {
                        Products attachProducts = attachList.get(index).get(k);
                        int attachPrice = attachProducts.price;
                        int attachImportant = attachProducts.important;

                        if (j >= price + attachPrice) {
                            dp[j] = Math.max(dp[j], dp[j - price - attachPrice] + important * price +
                                             attachImportant * attachPrice);
                        }
                    }
                    //如果有两个附件 还要考虑主件+两个附件 要不要为dp[j]构成满意度
                    if (attachList.get(index).size() > 1) {
                        Products attachProducts1 = attachList.get(index).get(0);
                        int attachPrice1 = attachProducts1.price;
                        int attachImportant1 = attachProducts1.important;
                        Products attachProducts2 = attachList.get(index).get(1);
                        int attachPrice2 = attachProducts2.price;
                        int attachImportant2 = attachProducts2.important;
                        int sumPrice = price + attachPrice1 + attachPrice2;
                        int sumImportant = important * price + attachImportant1 * attachPrice1 +
                                           attachImportant2 * attachPrice2;
                        if (j >= sumPrice) {
                            dp[j] = Math.max(dp[j], dp[j - sumPrice] + sumImportant);
                        }
                    }
                }
            }
        }
        System.out.println(dp[amount]);
    }
}

import java.util.*;

// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
    // 物品类
    private static class good{
        public int v;  // 物品价格
        public int p;  // 重要程度
        public int q;  // 是否是附件
        public good a1 = null;
        public good a2 = null;

        public good(int v, int p, int q){
            this.v = v;
            this.p = p;
            this.q = q;
        }

        public void setAppendGoods(good a){
            if(this.a1 == null)
                this.a1 = a;
            else
                this.a2 = a;
        }

        public boolean isFollowed(){
            if(this.a1 == null && this.a2 == null)
                return false;
            else    
                return true;
        }
    }

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int m = in.nextInt();  // 钱数
        int n = in.nextInt();  // 购买物品数
        
        List<good> input_good = new ArrayList<>();  // 存储输入值
        List<good> input_follow_good = new ArrayList<>();
        Map<Integer,Integer> map = new HashMap<Integer,Integer>();  // 存储主件位置
        int totalCount = 0;  // 记录主件原始数组中位置
        int mainCount = 0;  // 记录主件在主件数组中位置
        while(in.hasNext()){
            int v = in.nextInt();
            int p = in.nextInt();
            int q = in.nextInt();

            if(q != 0)
                input_follow_good.add(new good(v, p, q));
            else{
                input_good.add(new good(v, p ,q));
                map.put(totalCount,mainCount);
                mainCount++;
            }
            totalCount++;
        }

        int index = 0;
        // 插入辅件
        if(!input_follow_good.isEmpty()){
            for(good g:input_follow_good){
                index = map.get(g.q-1);
                input_good.get(index).setAppendGoods(g);
            }
        }
        int len = input_good.size();

        int[][] dp = new int[m+1][len+1];
        // 边界条件 - dp[0][j] = 0 | dp[i][0] = 0
        // 辅件计算 - 0 选1 选2 两个都选
        // 状态转换方程 (不带辅件)dp[i][j] = Max(dp[i][j-1], dp[i-input[j][0]][j-1] + input[j][0] * input[j][1])  (携带辅件)dp[i][j] = Max(dp[i][j-1], dp[i-input[j][0]][j-1] + input[j][0] * input[j][1], dp[i-input[j][0]-input[j1][0]][j-1] + input[j][0] * input[j][1] +input[j1][0] * input[j1][1], ***)
        for(int i=1; i<m+1; i++){
            for(int j=1; j<len+1; j++){
                good temp = input_good.get(j-1);
                dp[i][j] = dp[i][j-1];
                if(i-temp.v >= 0){
                    dp[i][j] = Math.max(dp[i][j-1], dp[i-temp.v][j-1]+temp.v*temp.p);
                    if(temp.isFollowed()){
                        if(temp.a1 != null && i-temp.v-temp.a1.v >= 0)  // 带附件1
                            dp[i][j] = Math.max(dp[i][j],dp[i-temp.v-temp.a1.v][j-1]+temp.v*temp.p+temp.a1.v*temp.a1.p);
                        if(temp.a2 != null && i-temp.v-temp.a2.v >= 0)  // 带附件2
                            dp[i][j] = Math.max(dp[i][j],dp[i-temp.v-temp.a2.v][j-1]+temp.v*temp.p+temp.a2.v*temp.a2.p);
                        if(temp.a1 != null && temp.a2 != null && i-temp.v-temp.a1.v-temp.a2.v >= 0)  // 带附件1和2
                            dp[i][j] = Math.max(dp[i][j],dp[i-temp.v-temp.a1.v-temp.a2.v][j-1]+temp.v*temp.p+temp.a1.v*temp.a1.p+temp.a2.v*temp.a2.p);
                    }
                }
            }
        }
        System.out.println(dp[m][len]);
    }
}