华为机试-016-中等-HJ16.购物单

发布于：2023-10-25 ⋅ 阅读:(67) ⋅ 点赞:(0)

华为机试-016-中等-HJ16.购物单

一、描述

  • 王强决定把年终奖用于购物，他把想买的物品分为两类：主件与附件，附件是从属于某个主件的，下表就是一些主件与附件的例子：
主件 附件
电脑 打印机，扫描仪
书柜 图书
书桌 台灯，文具
工作椅 无 
如果要买归类为附件的物品，必须先买该附件所属的主件，且每件物品只能购买一次。
每个主件可以有 0 个、 1 个或 2 个附件。附件不再有从属于自己的附件。
王强查到了每件物品的价格（都是 10 元的整数倍），而他只有 N 元的预算。除此之外，他给每件物品规定了一个重要度，用整数 1 ~ 5 表示。他希望在花费不超过 N 元的前提下，使自己的满意度达到最大。
满意度是指所购买的每件物品的价格与重要度的乘积的总和，假设设第i件物品的价格为v[i]，重要度为w[i]，共选中了k件物品，编号依次为j1、j2、j3、jk。
则满意度为：v[j1]*w[j1]+v[j2]*w[j2]+v[j3]*w[j3]+…+v[jk]*w[jk]。
（其中 * 为乘号）
请你帮助王强计算可获得的最大的满意度。

1.1、输入描述

  • 输入的第 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 是所属主件的编号）

1.2、输出描述

  • 输出一个正整数，为张强可以获得的最大的满意度。

二、示例

2.1、示例1

输入：

1000 5
800 2 0
400 5 1
300 5 1
400 3 0
500 2 0

输出：

2200

2.2、示例2

输入：

50 5
20 3 5
20 3 5
10 3 0
10 2 0
10 1 0

输出：

130

说明：

由第1行可知总钱数N为50以及希望购买的物品个数m为5；
第2和第3行的q为5，说明它们都是编号为5的物品的附件；
第4~6行的q都为0，说明它们都是主件，它们的编号依次为3~5；
所以物品的价格与重要度乘积的总和的最大值为10*1+20*3+20*3=130

三、答案（java）

3.1、方法一

  • 具体思路就是构造物品类，然后对主件判断是否有附件，若有附件则依次添加，根据主件、附件1、附件2的组合有四种情况

    • 只有主件
    • 主件+附件1
    • 主件+附件2
    • 主件+附件1+附件2

根据以上情况转化问题为经典的 01背包问题 ，接着就是套公式动态规划即可

package com.tzq.hwod;

import java.util.Scanner;

/**
 * @author tzq
 */
public class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int money = sc.nextInt();
		int n = sc.nextInt();
		if (n <= 0 || money <= 0)
			System.out.println(0);

		good[] Gs = new good[n + 1];
		for (int i = 1; i <= n; i++) {
			int v = sc.nextInt();
			int p = sc.nextInt();
			int q = sc.nextInt();
			Gs[i] = new good(v, p, q);

			if (q > 0) {
				if (Gs[q].a1 == 0) {
					Gs[q].setA1(i);
				} else {
					Gs[q].setA2(i);
				}
			}
		}

		int[][] dp = new int[n + 1][money + 1];
		for (int i = 1; i <= n; i++) {
			int v = 0, v1 = 0, v2 = 0, v3 = 0, tempdp = 0, tempdp1 = 0, tempdp2 = 0, tempdp3 = 0;

			v = Gs[i].v;

			tempdp = Gs[i].p * v; // 只有主件

			if (Gs[i].a1 != 0) {// 主件加附件1
				v1 = Gs[Gs[i].a1].v + v;
				tempdp1 = tempdp + Gs[Gs[i].a1].v * Gs[Gs[i].a1].p;
			}

			if (Gs[i].a2 != 0) {// 主件加附件2
				v2 = Gs[Gs[i].a2].v + v;
				tempdp2 = tempdp + Gs[Gs[i].a2].v * Gs[Gs[i].a2].p;
			}

			if (Gs[i].a1 != 0 && Gs[i].a2 != 0) {// 主件加附件1和附件2
				v3 = Gs[Gs[i].a1].v + Gs[Gs[i].a2].v + v;
				tempdp3 = tempdp + Gs[Gs[i].a1].v * Gs[Gs[i].a1].p + Gs[Gs[i].a2].v * Gs[Gs[i].a2].p;
			}

			for (int j = 1; j <= money; j++) {
				if (Gs[i].q > 0) { // 当物品i是附件时,相当于跳过
					dp[i][j] = dp[i - 1][j];
				} else {
					dp[i][j] = dp[i - 1][j];
					if (j >= v && v != 0)
						dp[i][j] = Math.max(dp[i][j], dp[i - 1][j - v] + tempdp);
					if (j >= v1 && v1 != 0)
						dp[i][j] = Math.max(dp[i][j], dp[i - 1][j - v1] + tempdp1);
					if (j >= v2 && v2 != 0)
						dp[i][j] = Math.max(dp[i][j], dp[i - 1][j - v2] + tempdp2);
					if (j >= v3 && v3 != 0)
						dp[i][j] = Math.max(dp[i][j], dp[i - 1][j - v3] + tempdp3);
				}
			}
		}
		System.out.println(dp[n][money]);

	}

	/**
	 * 定义物品类
	 */
	private static class good {
		public int v; // 物品的价格
		public int p; // 物品的重要度
		public int q; // 物品的主附件ID

		public int a1 = 0; // 附件1ID
		public int a2 = 0; // 附件2ID

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

		public void setA1(int a1) {
			this.a1 = a1;
		}

		public void setA2(int a2) {
			this.a2 = a2;
		}
	}
}

在这里插入图片描述

四、答案（python 3）

4.1、方法一

其实这题就是0-1背包问题
首先来看一下经典背包问题，稍作修改就可以得出这题的解答

0-1背包问题

问题描述：有一个背包可以装物品的总重量为W，现有N个物品，每个物品中w[i]，价值v[i]，用背包装物品，能装的最大价值是多少？

定义状态转移数组dp[i][j]，表示前i个物品，背包重量为j的情况下能装的最大价值。

例如，dp[3][4]=6，表示用前3个物品装入重量为4的背包所能获得的最大价值为6，此时并不是3个物品全部装入，而是3个物品满足装入背包的条件下的最大价值。

状态转移方程：

dp[i][j] = max(dp[i-1][j], dp[i-1][j-w[i]]+v[i])

dp[i-1][j]表示当前物品不放入背包，dp[i-1][j-w[i]]+v[i]表示当前物品放入背包，即当前第i个物品要么放入背包，要么不放入背包。

dp = [[0]*(n+1) for _ in range(m+1)]
for i in range(1,m+1):
    for j in range(1,n+1):
        if j-w[i]>=0:
            dp[i][j] = max(dp[i-1][j], dp[i-1][j-w[i]]+v[i])
        else:
            dp[i][j] = dp[i-1][j]
return dp[m][n]

现在来看下购物车的解题思路

购物车本质上还是0-1背包问题，只不过多了主件和附件。假设先不看附件，那么就和0-1背包一样了。附件不能单独出现，要依赖于主件。

对应于背包问题，主件的个数就是物品的个数，考虑每个主件时要考虑可能出现的情况。

输入例子:
1000 5
800 2 0
400 5 1
300 5 1
400 3 0
500 2 0

在当前的例子当中物品的个数就是3。

考虑每个物品时要考虑每种可能出现的情况，1、主件，2、主件+附件1，3、主件+附件2，4、主件+附件1+附件2，不一定每种情况都出现，只有当存在附件时才会出现对应的情况。

w[i][k]表示第i个物品的第k种情况，k的取值范围0~3，分别对应以上4中情况，v[i][k]表示第i个物品对应第k种情况的价值，现在就把购物车问题转化为了0-1背包问题。

状态转移方程可以定义为

dp[i][j] = max(dp[i-1][j],dp[i-1][j-w[i][k]]+v[i][k])

dp[i-1][j]表示当前物品不放入背包，w[i][k]表示第i个主件对应第k中情况，即当前第i个物品的4中情况中价值最大的要么放入背包，要么不放入背包。

需要注意：dp[i][j] = max(物品不放入背包，主件，主件+附件1，主件+附件2，主件+附件1+附件2)

dp = [[0]*(n+1) for _ in range(m+1)]
for i in range(1,m+1):
    for j in range(1,n+1):
        max_i = dp[i-1][j]
        for k in range(len(w[i])):
            if j-w[i][k]>=0:
                max_i = max(max_i, dp[i-1][j-w[i][k]]+v[i][k])
        dp[i][j] = max_i
print(dp[m][n])

具体代码如下：

n, m = map(int,input().split())
primary, annex = {}, {}
for i in range(1,m+1):
    x, y, z = map(int, input().split())
    if z==0:#主件
        primary[i] = [x, y]
    else:#附件
        if z in annex:#第二个附件
            annex[z].append([x, y])
        else:#第一个附件
            annex[z] = [[x,y]]
m = len(primary)#主件个数转化为物品个数
dp = [[0]*(n+1) for _ in range(m+1)]
w, v= [[]], [[]]
for key in primary:
    w_temp, v_temp = [], []
    w_temp.append(primary[key][0])#1、主件
    v_temp.append(primary[key][0]*primary[key][1])
    if key in annex:#存在主件
        w_temp.append(w_temp[0]+annex[key][0][0])#2、主件+附件1
        v_temp.append(v_temp[0]+annex[key][0][0]*annex[key][0][1])
        if len(annex[key])>1:#存在两主件
            w_temp.append(w_temp[0]+annex[key][1][0])#3、主件+附件2
            v_temp.append(v_temp[0]+annex[key][1][0]*annex[key][1][1])
            w_temp.append(w_temp[0]+annex[key][0][0]+annex[key][1][0])#3、主件+附件1+附件2
            v_temp.append(v_temp[0]+annex[key][0][0]*annex[key][0][1]+annex[key][1][0]*annex[key][1][1])
    w.append(w_temp)
    v.append(v_temp)
for i in range(1,m+1):
    for j in range(10,n+1,10):#物品的价格是10的整数倍
        max_i = dp[i-1][j]
        for k in range(len(w[i])):
            if j-w[i][k]>=0:
                max_i = max(max_i, dp[i-1][j-w[i][k]]+v[i][k])
        dp[i][j] = max_i
print(dp[m][n])

继续优化

现在的时间复杂度是O(mn)，时间复杂度已经无法优化，空间复杂度O(mn)，可以继续优化到O(n)。

回顾下状态转移方程：
dp[i][j] = max(dp[i-1][j], dp[i-1][j-w[i]]+v[i])

dp[i]只依赖dp[i-1]，状态转移方程就可以改为：
dp[j] = max(dp_pre[j], dp_pre[j-w[i]]+v[i])

dp_pre[j]存储上一次得到的值，现在只需要2*n的空间就能得到结果。继续观察可以发现，其实只用一个一维dp数组就行，不需要额外的辅助数组。让j从n到1遍历，此时每次更新的dp[j]时，max函数中dp[j]和 dp[j-w[i]]都是上次保存的值。

状态转移方程变为：
for j in [n…1]:
dp[j] = max(dp[j], dp[j-w[i]]+v[i])

如果从1到n遍历的话dp[j-w[i]]不能保证还是上次的值，这也进一步说明为什么用一维数组时需要从n到1遍历。

优化后的代码如下：

n, m = map(int,input().split())
primary, annex = {}, {}
for i in range(1,m+1):
    x, y, z = map(int, input().split())
    if z==0:
        primary[i] = [x, y]
    else:
        if z in annex:
            annex[z].append([x, y])
        else:
            annex[z] = [[x,y]]
dp = [0]*(n+1)
for key in primary:
    w, v= [], []
    w.append(primary[key][0])#1、主件
    v.append(primary[key][0]*primary[key][1])
    if key in annex:#存在附件
        w.append(w[0]+annex[key][0][0])#2、主件+附件1
        v.append(v[0]+annex[key][0][0]*annex[key][0][1])
        if len(annex[key])>1:#附件个数为2
            w.append(w[0]+annex[key][1][0])#3、主件+附件2
            v.append(v[0]+annex[key][1][0]*annex[key][1][1])
            w.append(w[0]+annex[key][0][0]+annex[key][1][0])#4、主件+附件1+附件2
            v.append(v[0]+annex[key][0][0]*annex[key][0][1]+annex[key][1][0]*annex[key][1][1])
    for j in range(n,-1,-10):#物品的价格是10的整数倍
        for k in range(len(w)):
            if j-w[k]>=0:
                dp[j] = max(dp[j], dp[j-w[k]]+v[k])    
print(dp[n])

在这里插入图片描述

网站公告

今日签到

点亮在社区的每一天
去签到

热门文章

最新发布