描述

如果要买归类为附件的物品，必须先买该附件所属的主件。每个主件可以有 0 个、 1 个或 2 个附件。附件不再有从属于自己的附件。王强想买的东西很多，为了不超出预算，他把每件物品规定了一个重要度，分为 5 等：用整数 1 ~ 5 表示，第 5 等最重要。他还从因特网上查到了每件物品的价格（都是 10 元的整数倍）。他希望在不超过 N 元（可以等于 N 元）的前提下，使每件物品的价格与重要度的乘积的总和最大。

设第 j 件物品的价格为 v[j] ，重要度为 w[j] ，共选中了 k 件物品，编号依次为 j 1 ， j 2 ，……， j k ，则所求的总和为：

v[j 1 ]*w[j 1 ]+v[j 2 ]*w[j 2 ]+ … +v[j k ]*w[j k ] 。（其中 * 为乘号）

请你帮助王强设计一个满足要求的购物单。

输入描述：输入的第 1 行，为两个正整数，用一个空格隔开：N m

（其中 N （ <32000 ）表示总钱数， m （ <60 ）为希望购买物品的个数。）

从第 2 行到第 m+1 行，第 j 行给出了编号为 j-1 的物品的基本数据，每行有 3 个非负整数 v p q

（其中 v 表示该物品的价格（ v<10000 ）， p 表示该物品的重要度（ 1 ~ 5 ）， q 表示该物品是主件还是附件。如果 q=0 ，表示该物品为主件，如果 q>0 ，表示该物品为附件， q 是所属主件的编号）

输出描述： 输出文件只有一个正整数，为不超过总钱数的物品的价格与重要度乘积的总和的最大值（ <200000 ）。

解法

此题考查的是动态规划，是0-1背包问题的升级版，称为依赖背包问题。对于每个附件来说，都必须选取其对应的主件。这就是一种依赖关系。不过这里的依赖关系比较简单，我们采取这样一种方式处理。因为每个主件最多只有两个附件，我们可以将每个主件和不同数量的附件组合成一个个新的物品。有点像多重背包的二进制优化。这样每个主件代表一个物品组，每个物品组里的物品是主件和数量不同的附件组成的新物品，这样问题就变成了一个分组背包问题。

按照题意，可以分为以下5种场景。

  • 不买。j<w(i) V(i,j)=V(i-1,j)
  • 只买主件。
  • 买主件、附件1。
  • 买主件、附件2。
  • 买主件、附件1、附件2。

代码实现如下： 

/* 
* Copyright (c) waylau.com, 2022. All rights reserved.
 */ package com.waylau.nowcoder.exam.oj.huawei; import java.util.Scanner; /**
 * HJ16 购物单. 输入描述：输入的第 1 行，为两个正整数，用一个空格隔开：N m 
 * （其中 N （ <32000 ，是10的倍数）表示总钱数， m （ <60）为希望购买物品的个数。） 
 * 从第 2 行到第 m+1 行，第 j 行给出了编号为 j-1 的物品的基本数据，每行有 3 个非负整数 v p q 
 * （其中 v 表示该物品的价格（ v<10000 ，是10的倍数 ）， p 表示该物品的重要度（ 1 ~ 5 ）， q 表示该物品是主件还是附件。
 * 如果 q=0 ，表示该物品为主件，如果 q>0 ，表示该物品为附件， q 是所属主件的编号） 。
 * 输出描述：输出文件只有一个正整数，为不超过总钱数的物品的价格与重要度乘积的总和的最大值（<200000 ）。
 *
 * @author <a href="https://waylau.com">Way Lau</a>
 * @since 2022-08-11
 */ public class HJ016ShoppingList { public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt() / 10; // 总钱数，由于是10的倍数，所以先除以10，节省空间         int m = sc.nextInt();// 总物品数目         int[][] prices = new int[N + 1][3];
        int[][] weights = new int[m + 1][3];
        sc.nextLine();
        
        for (int i = 1; i <= m; i++) {
            int v = sc.nextInt() / 10; // 需要的钱，由于是10的倍数，所以先除以10，             int p = sc.nextInt() * v;// 钱*重要度             int q = sc.nextInt();
            sc.nextLine();
            if (q == 0) {// 主件直接加就行                 prices[i][0] = v;
                weights[i][0] = p;
            } else if (prices[q][1] == 0) {// 从件先试着赋值到主件的第一个位置去                 prices[q][1] = v;
                weights[q][1] = p;
            } else {// 1号有从件后赋值到从件2                 prices[q][2] = v;
                weights[q][2] = p;
            }
        }
        
        int[] dp = new int[N + 1];// 压缩空间到1维         for (int i = 1; i <= m; i++) {// 遍历所有物品             for (int j = N; j >= 1; j--) {// 从后向前遍历防止出错                 // 分为四种情况：只放主，放主+从1，放主+从2，放主+从1+从2                 int p1 = prices[i][0];// 从件都为0的                 int w1 = weights[i][0];
                int p2 = prices[i][1];
                int w2 = weights[i][1];
                int p3 = prices[i][2];
                int w3 = weights[i][2];
                
                if (j - p1 >= 0) {
                    dp[j] = Math.max(dp[j],    dp[j - p1] + w1);
                }
                if (j - p1 - p2 >= 0) {
                    dp[j] = Math.max(dp[j],    dp[j - p1 - p2] + w1 + w2);
                }
                if (j - p1 - p3 >= 0) {
                    dp[j] = Math.max(dp[j],    dp[j - p1 - p3] + w1 + w3);
                }
                if (j - p1 - p2 - p3 >= 0) {
                    dp[j] = Math.max(dp[j],    dp[j - p1 - p2 - p3] + w1 + w2 + w3);
                }
            }
        }
        
        System.out.println(dp[N] * 10);// 由于是10的倍数，所以乘以10         sc.close();
    }

}复制

输入：

1000 5

800 2 0

400 5 1

300 5 1

400 3 0

500 2 0

输出：

2200

输入：

50 5

20 3 5

20 3 5

10 3 0

10 2 0

10 1 0

输出：

130

参考引用