題目

链接

描述

王强决定把年终奖用于购物，他把想买的物品分为两类：主件与附件，附件是从属于某个主件的，下表就是一些主件与附件的例子：

如果要买归类为附件的物品，必须先买该附件所属的主件，且每件物品只能购买一次。

每个主件可以有 0 个、 1 个或 2 个附件。附件不再有从属于自己的附件。

王强查到了每件物品的价格（都是 10 元的整数倍），而他只有 N 元的预算。除此之外，他给每件物品规定了一个重要度，用整数 1 ~ 5 表示。他希望在花费不超过 N 元的前提下，使自己的满意度达到最大。

满意度是指所购买的每件物品的价格与重要度的乘积的总和，假设设第i件物品的价格为v[i]，重要度为w[i]，共选中了k件物品，编号依次为j1​,j2​,...,jk​，则满意度为：v[j1​]∗w[j1​]+v[j2​]∗w[j2​]+…+v[jk​]∗w[jk​]。（其中 * 为乘号）

请你帮助王强计算可获得的最大的满意度。

输入描述：

输入的第 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

输入：

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

输出：

2200

示例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  

代碼：

from re import M

first_line = input().split(" ")
N = int(int(first_line[0]) / 10)
m = int(first_line[1])

# data = [[0] * 6] * (m + 1) 浅拷贝

data = [[0 for i in range(6)] for j in range(m+1)]
for index in range(1, m + 1):
    line = input().split(" ")

    v = int(int(line[0]) / 10)
  
    p = int(line[1])
    q = int(line[2])

    if q == 0:
        data[index][0] = v
        data[index][1] = p
        
    elif data[q][2] == 0:
        data[q][2] = v
        data[q][3] = p
    else:
        data[q][4] = v
        data[q][5] = p
    # print(data)

 

# dp = [[0] * (N + 1)] * (m + 1)
dp = [[0 for i in range(N+ 2)] for j in range(m+1)]
for i in range(1, m + 1):
    for j in range(1, N + 1):
        pricePrime = data[i][0]
        priceAtta1 = data[i][2]
        priceAtta2 = data[i][4]

        priorPrime = data[i][1]
        priorAtta1 = data[i][3]
        priorAtta2 = data[i][5]
        if j >= pricePrime :
            dp[i][j] =  max(dp[i - 1][j - pricePrime] + priorPrime * pricePrime, dp[i - 1][j]) 
        else:
            dp[i][j] = dp[i - 1][j]
        if j >=(pricePrime + priceAtta1): 
            dp[i][j] = max(dp[i - 1][j - pricePrime - priceAtta1]+ pricePrime * priorPrime + priceAtta1 * priorAtta1, dp[i ][j]) 
        
        if j >= (pricePrime + priceAtta2):
            dp[i][j] = max(dp[i - 1][j - pricePrime - priceAtta2]+ pricePrime * priorPrime + priceAtta2 * priorAtta2, dp[i ][j])
     
        if j >= (pricePrime + priceAtta1 + priceAtta2):
            dp[i][j] = max(dp[i - 1][j - pricePrime - priceAtta1- priceAtta2]+ pricePrime * priorPrime + priceAtta1 * priorAtta1 + priceAtta2 * priorAtta2, dp[i][j]) 
        
        
print(dp[m][N] * 10)
    

總結：

• 目的：充分利用 不同物品的单价和 重要度 获得 最大的满意度
• 有三個元素：单价、重要度、滿意度
• 关系：单价*重要度=滿意度
• 总价 有限制
• 单个物品 有附属 物品（附属物品的数量有限制）
• 二维数组dp[i][j]
• i 可以用来表示第几个物品
• j 可以用来表示物品的价格
• dp[i][j]表示 满意度
• 题意信息：
• 每件物品只能购买一次：给出来的物品只能使用一次，不能重复使用
• 物品 价格 都是 10 元的整数倍：可以知道价格 j可以 缩小10倍，减少数组的j 数值 过大
• 每个主件可以有 0 个、 1 个或 2 个附件： 附件有数量限制
• q 是所属主件的编号：可以用来 归类 附件 属于哪个 主机
• 问题：
• python 创建 二维数组时，出现了浅拷贝和深拷贝的问题，多多注意一下！

參考目錄

python 二维数组 的浅拷贝问题 ： https://blog.csdn.net/flyingluohaipeng/article/details/129828525