题解 | 史上最全解析，0-1背包问题加了一些情况#购物单#

之前没做过动态规划，这道题理解了我两天，其实就是很简单的01背包问题，就是每个物品都会有四种情况，然后就是不加入物品或者加入物品的四种情况中的一种，下面是题解和最详细的代码注释

/**
 * @author TanJie
 * @date 2023/10/1 17:16
 */


import java.util.Arrays;
import java.util.Scanner;

/**
 * 输入的第 1 行，为两个正整数N，m，用一个空格隔开：
 * （其中 N （ N<32000 ）表示总钱数， m （m <60 ）为可购买的物品的个数。）
 * 从第 2 行到第 m+1 行，第 j 行给出了编号为 j-1 的物品的基本数据，每行有 3 个非负整数 v p q
 * （其中 v 表示该物品的价格（ v<10000 ）， p 表示该物品的重要度（ 1 ~ 5 ），
 * q 表示该物品是主件还是附件。如果 q=0 ，表示该物品为主件，如果 q>0 ，表示该物品为附件， q 是所属主件的编号）
 */

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int money = scanner.nextInt();       //总金额
        int goods_num = scanner.nextInt();    //商品数量
        if (money == 0 || goods_num == 0) {
            System.out.println(0);
        }

        //建立商品数组，下标就是表示商品编号，所以数组长度加1，商品编号从1开始
        Good[] goods = new Good[goods_num + 1];
        //i代表商品的顺序编号    设置所有商品的基础属性
        for (int i = 1; i <= goods_num; i++) {
            int price = scanner.nextInt();
            int importance = scanner.nextInt();
            int annexId = scanner.nextInt();             //0：主件，>0： 附件
            int satisfaction = price * importance;      //满意度
            goods[i] = new Good(price, importance, annexId, satisfaction);
        }

        for (int i = 1; i <= goods_num; i++) {
            //如果是附件
            if (goods[i].annexId > 0) {
                if (goods[goods[i].annexId].a1id == 0) {
                    goods[goods[i].annexId].a1id = i;
                } else {
                    goods[goods[i].annexId].a2id = i;
                }
            }
        }

        //计算所有主件的关联属性，把四种情况合并为一种
        for (int i = 1; i <= goods_num; i++) {

            //如果是主件，计算这个主件所对应四种情况的所有价格表，满意度
            if (goods[i].annexId == 0) {
                if (goods[i].a1id != 0) {
                    goods[i].price1 = goods[i].price + goods[goods[i].a1id].price;
                    goods[i].satisfaction1 = goods[i].satisfaction + goods[goods[i].a1id].satisfaction;
                }
                if (goods[i].a2id != 0) {
                    goods[i].price2 = goods[i].price + goods[goods[i].a2id].price;
                    goods[i].satisfaction2 = goods[i].satisfaction + goods[goods[i].a2id].satisfaction;
                }
                if (goods[i].a1id != 0 && goods[i].a2id != 0) {
                    //这里不能简单的用price1+price2-price的方式来解决，因为prices1和price2都可能为0，satisfaction同理
//                    goods[i].priceAll = goods[i].price1 + goods[i].price2 - goods[i].price;
//                    goods[i].satisfactionALL = goods[i].satisfaction1 + goods[i].satisfaction2 - goods[i].satisfaction;

                    goods[i].priceAll = goods[i].price + goods[goods[i].a1id].price + goods[goods[i].a2id].price;
                    goods[i].satisfactionALL = goods[i].satisfaction + goods[goods[i].a1id].satisfaction + goods[goods[i].a2id].satisfaction;
                }
            }
        }

        //定义状态转移数组，该问题转化为01背包问题
        //商品数量从1遍历到goods_num, 金额大小从0遍历到money
        int[][] dp = new int[goods_num + 1][money + 1];     //dp[0][] = 0 第一行初始化为0，从第2行开始遍历
        //从i个物品里面挑选，选出满意度最大的组合
        for (int i = 1; i <= goods_num; i++) {
            //当金额为j时，满意度最大的组合
            for (int j = 0; j <= money; j++) {
                //不管是不是附件，每次都要更新为前一个状态，不然dp[i][j]就是0，
                // 然后就是放入这四种状态中的一种和不不放入比较，也就是上一次的状态
                dp[i][j] = dp[i - 1][j];
                //如果是附件,则不参与挑选
                if (goods[i].annexId != 0) {
                    continue;
                }
                //对于第i个物品，当金额为j时最大满意度, 对于每个i，又分为这四种情况，在这四种情况中选
                //因为这四种情况是顺序执行，所以要在当前状态中比较最大值
                //dp[i][j] = Math.max(dp[i][j], dp[i - 1][j - p] + s);
                if (j >= goods[i].price) {
                    dp[i][j] = Math.max(dp[i][j], dp[i - 1][j - goods[i].price] + goods[i].satisfaction);
                }
                if (goods[i].a1id != 0 && j >= goods[i].price1) {
                    dp[i][j] = Math.max(dp[i][j], dp[i - 1][j - goods[i].price1] + goods[i].satisfaction1);
                }
                if (goods[i].a2id != 0 && j >= goods[i].price2) {
                    dp[i][j] = Math.max(dp[i][j], dp[i - 1][j - goods[i].price2] + goods[i].satisfaction2);
                }
                if (goods[i].a1id != 0 && goods[i].a2id != 0 && j >= goods[i].priceAll) {
                    dp[i][j] = Math.max(dp[i][j], dp[i - 1][j - goods[i].priceAll] + goods[i].satisfactionALL);
                }
            }
        }
        //最大满意度为数组中最后一个元素
        System.out.println(dp[goods_num][money]);
//        System.out.println(Arrays.deepToString(dp));


    }
}

/**
 * 商品类
 */
class Good {
    int price;         //价格

    int price1;       //主件+附件1价格

    int price2;       //主件+附件2价格

    int priceAll;     //主键+附件1和2的价格

    int importance;    //重要度

    int annexId;        //商品编号 0为主商品，其他为编号为该id的主商品附件

    int satisfaction;   //满意度

    int satisfaction1;  //主件加附件1的满意度

    int satisfaction2;  //主件加附件2的满意度

    int satisfactionALL;  //主件加附件1和2的满意度

    int a1id;          //附件1 商品编号

    int a2id;          //附件2 商品编号

    public Good(int price, int importance, int annexId, int satisfaction) {
        this.price = price;
        this.importance = importance;
        this.annexId = annexId;
        this.satisfaction = satisfaction;
    }

}