首页 > 试题广场 >

购物单

[编程题]购物单
  • 热度指数：476343 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 32M，其他语言64M
  • 算法知识视频讲解
\hspace{15pt}王强决定把年终奖用于购物，他把想买的物品分为两类：主件与附件。
\hspace{23pt}\bullet\,主件可以没有附件，至多有 2 个附件。附件不再有从属于自己的附件。
\hspace{23pt}\bullet\,若要购买某附件，必须先购买该附件所属的主件，且每件物品只能购买一次。

\hspace{15pt}王强查到了 m 件物品的价格，而他只有 n 元的预算。为了先购买重要的物品，他给每件物品规定了一个重要度，用整数 1 \sim 5 表示。他希望在不超过预算的前提下，使满意度最大。

\hspace{15pt}满意度定义为所购每件物品价格与重要度乘积之和。具体地说，记第 i 件物品的价格为 v_i，重要度为 w_i；若共选中 k 件物品，编号为 j_1,j_2,\dots,j_k，则满意度计算为：
\sum\limits_{t=1}^{k} v_{j_t} \times w_{j_t} = v_{j_1} w_{j_1} + v_{j_2} w_{j_2} + \dots + v_{j_k} w_{j_k}

\hspace{15pt}请你帮助王强计算可获得的最大的满意度。

输入描述:
\hspace{15pt}第一行输入两个整数 n, m \left(1 \leqq n \leqq 3 \times 10^4;\ 1 \leqq m \leqq 60\right) 代表预算、查询到的物品总数。
\hspace{15pt}此后 m 行，第 i 行输入三个整数 v_i, w_i, q_i \left(1 \leqq v_i \leqq 10^4;\ 1 \leqq w_i \leqq 5;\ 0 \leqq q_i \leqq m\right) 代表第 i 件物品的价格、重要度、主件编号。特别地，q_i = 0 代表该物品为主件，否则表示该附件从属于主件 q_i。编号即输入顺序，从 1 开始。

\hspace{15pt}特别地，保证全部物品的价格 v 均为 10 的倍数；且每个主件的附件数不超过 2 个。


输出描述:
\hspace{15pt}在一行上输出一个整数，代表王强可获得的最大满意度。
示例1

输入

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

输出

130

说明

\hspace{15pt}在这个样例中，第三、四、五件物品为主件，第一、二件物品为第五件物品的附件。这就意味着，如果购买了第一件物品或第二件物品，则必须购买第五件物品；但是特别地，如果同时购买了第一件物品和第二件物品，则只需要购买一次第五件物品。
\hspace{15pt}我们可以证明，购买一、二、五件商品，获得的满意度最大，为 20 \times 3 + 20 \times 3 + 10 \times 1 = 130。
示例2

输入

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

输出

2200

备注:
本题已于下方时间节点更新，请注意题解时效性：
1. 2025-05-15 更新题面，新增几组hack数据（暂未进行重测）。
2. 2024-12-13 更新题面。
算法知识视频讲解
添加回答
Python3
Drsanwujiang头像 Drsanwujiang
from dataclasses import dataclass, field

@dataclass
class Product:
    id: int
    price: int
    priority: int
    primary_id: int
    is_primary: bool = field(init=False)
    satisfaction: int = field(init=False)

    def __post_init__(self):
        self.is_primary = self.primary_id == 0
        self.satisfaction = self.price * self.priority

budget, products = map(int, input().split())
all_products: dict[int, Product] = {}
primary_products: dict[int, Product] = {}
attachments_map: dict[int, list[Product]] = {}

for i in range(1, products + 1):
    current_product = Product(i, *map(int, input().split()))
    all_products[current_product.id] = current_product

    if current_product.is_primary:
        primary_products[current_product.id] = current_product
        attachments_map[current_product.id] = []

for product in all_products.values():
    if not product.is_primary:
        attachments_map[product.primary_id].append(product)

dp = [0] * (budget + 1)

for primary_id, primary_product_obj in primary_products.items():
    current_attachments = attachments_map.get(primary_id, [])
    options_to_consider = []

    options_to_consider.append((primary_product_obj.price, primary_product_obj.satisfaction))

    if len(current_attachments) >= 1:
        attach1 = current_attachments[0]
        options_to_consider.append((
            primary_product_obj.price + attach1.price,
            primary_product_obj.satisfaction + attach1.satisfaction
        ))
   
    if len(current_attachments) >= 2:
        attach2 = current_attachments[1]
        options_to_consider.append((
            primary_product_obj.price + attach2.price,
            primary_product_obj.satisfaction + attach2.satisfaction
        ))

    if len(current_attachments) >= 2:
        attach1 = current_attachments[0]
        attach2 = current_attachments[1]
        options_to_consider.append((
            primary_product_obj.price + attach1.price + attach2.price,
            primary_product_obj.satisfaction + attach1.satisfaction + attach2.satisfaction
        ))
   
    for j in range(budget, -1, -1):
        for cost, value in options_to_consider:
            if j >= cost:
                dp[j] = max(dp[j], dp[j - cost] + value)

print(dp[budget])
发表于 2025-05-09 18:19:29 回复(0)
Python3
kk冲华为od头像 kk冲华为od 
n, m = map(int, input().split())
n = n // 10  # 预算缩小为十分之一
items = []
for _ in range(m):
    v, p, q = map(int, input().split())
    v = v // 10  # 处理后的价格
    items.append((v, p, q))

main_items = {}  # 主件字典，键是主件的输入顺序号（1-based）

# 第一次遍历，找出所有主件
for i in range(m):
    v, p, q = items[i]
    if q == 0:
        main_id = i + 1  # 主件编号为输入顺序号（1-based）
        main_items[main_id] = {
            'v': v,
            'p': p,
            'attachments': []
        }

# 第二次遍历，处理附件
for i in range(m):
    v, p, q = items[i]
    if q != 0:
        main_id = q
        if main_id in main_items:
            main_items[main_id]['attachments'].append((v, p))

# 生成每个主件的所有可能的选项
groups = []
for main_id in main_items:
    main_data = main_items[main_id]
    v_processed = main_data['v']
    p = main_data['p']
    attachments = main_data['attachments']
    k = len(attachments)
    options = []
    for mask in range(0, 1 << k):
        total_v = v_processed
        total_s = (v_processed * 10) * p  # 原价是v_processed * 10，乘以重要度p
        for i in range(k):
            if mask & (1 << i):
                a_v, a_p = attachments[i]
                total_v += a_v
                total_s += (a_v * 10) * a_p  # 原价是a_v *10，乘以重要度a_p
        options.append((total_v, total_s))
    groups.append(options)

# 动态规划处理分组背包问题
dp = [0] * (n + 1)
for group in groups:
    for j in range(n, -1, -1):
        max_val = dp[j]
        for (cost, sat) in group:
            if j >= cost and dp[j - cost] + sat > max_val:
                max_val = dp[j - cost] + sat
        dp[j] = max_val

print(dp[n])


发表于 2025-05-03 00:04:49 回复(0)
Python3
drewfranklin头像 drewfranklin 
首先应该明确示例的定义，示例对于理解题目来说非常关键
输入第一行，1000 是总预算（total_budget） 5 指总的物品数量（包含主件附件）
第二行之后的就是每个物品的描述数据了
第一列800 400 300 400 500 这些表示物品价格，第二列的数字是物品的重要度
第三列很关键，，非0 数字都表示这个物品是附件，0 表示这个物品是主件。
非0的同时这个数字是和主件有绑定关系的，比如是1，表示这个是主件1 的附件，那么主件1 是谁就很关键，
找错主件结果就完全不对了，所以这里要考虑我们在存储主件的时候，同时要保留的是主件的索引，从题目中来看，主件从1 开始
所以遇到第1行是0 的数据，就得更新主件索引为1（i + 1），同时将附件数据绑定上去，这样算是成功了一半了。

多重背包很关键的一点考虑在物品不能重复购买，这就说明你在预算计算的时候，需要考虑是倒序遍历
必须的，不然重复计算了，这点可能比较难理解，可以带入一下就能想的比较清晰，还有一点就是遍历时的stop 点
v - 1 , 当j >= v 的时候进行遍历即可
思考，先从主件开始，主件+附件1 主件+附件2 主件+附件1+附件2，依次更新dp[j]

#购物单 这是一个多重背包问题,购买主件后，可以不购买附件，也可以购买1件或者2件附件，不能重复购买，求最大的满意度
#首先定义这个输入输出
'''
1000 总预算 5物品数量
800 2 满意度 0 主件0
400 5 1 主件0 的附件1
300 5 1 主件0 的附件2
400 3 0 主件1
500 2 0 主件2
'''
import sys
total_budget, num_items = map(int, sys.stdin.readline().rstrip().split())

#存储主件
main_items = []
attachments = {}
i = 0
while i < num_items:
    v, p, q = map(int, sys.stdin.readline().rstrip().split())
    if q == 0: #存储主件
        main_items.append((v, p, i + 1))
    else: #附件
        if q not in attachments:
            attachments[q] = []
        attachments[q].append((v, p))
    i += 1

dp = [0] * (total_budget + 1)
#选择主件
for  v, p, idx in main_items:
    #从后往前遍历，避免重复选择
    for j in range(total_budget, v - 1, -1):
        dp[j] = max(dp[j], dp[j - v] + v * p)
        #计算附件
        if idx in attachments:
            for av, ap in attachments[idx]:
                if j >= v + av:
                    dp[j] = max(dp[j], dp[j - v - av] + v * p + av * ap)
            if len(attachments[idx]) == 2:
                av1, ap1 = attachments[idx][0]
                av2, ap2 = attachments[idx][1]
                if j >= av1 + av2 + v:
                    dp[j] = max(dp[j], dp[j - v - av1 - av2] + v * p + av1 * ap1 + av2 * ap2)

print(dp[total_budget])

发表于 2024-11-15 13:21:59 回复(1)
Python3
Cyber2077头像 Cyber2077 
def max_satisfaction(n, items):
    # 初始化物品信息（主件及其附件）
    main_parts, annex_parts = {}, {}
    for i, (v, p, q) in enumerate(items):
        if q == 0:  # 主件
            main_parts[i + 1] = [v, v * p]
        else:  # 附件
            if q in annex_parts:
                annex_parts[q].append([v, v * p])
            else:
                annex_parts[q] = [[v, v * p]]

    # 动态规划数组
    dp = [0] * (n + 1)

    # 遍历所有主件
    for key, value in main_parts.items():
        v, s = [], []  # 物品组合的 价格，满意 度列表
        # 1、主件
        v.append(value[0])
        s.append(value[1])
        if key in annex_parts:  # 该主键存在附件
            # 2、主件+附件1
            v.append(v[0] + annex_parts[key][0][0])
            s.append(s[0] + annex_parts[key][0][1])
            if len(annex_parts[key]) > 1:  # 附件个数为2
                # 3、主件+附件2
                v.append(v[0] + annex_parts[key][1][0])
                s.append(s[0] + annex_parts[key][1][1])
                # 4、主件+附件1+附件2
                v.append(v[0] + annex_parts[key][0][0] + annex_parts[key][1][0])
                s.append(s[0] + annex_parts[key][0][1] + annex_parts[key][1][1])

        for j in range(n, v[0] - 10, -10):  # 物品的价格是10的整数倍，从 总钱数~主件价格 遍历
            for k in range(len(v)):  # 遍历当前主件下的物品组合
                if j >= v[k]:  # 总钱数 >= 当前物品组合的钱数
                    # dp[j]: 预算为j时，可以获得的最大满意度
                    # dp[j - v[k]] + s[k]: 表示如果选择购买当前物品组合，在剩余的预算 j-v[k] 下所能获得的最大满意度，加上当前物品组合的满意度
                    dp[j] = max(dp[j], dp[j - v[k]] + s[k])  # 不买或买

    return dp[n]


# 输入
n, m = map(int, input().split())  # 总钱数，物品个数
items = [tuple(map(int, input().split())) for _ in range(m)]  # 物品数据
# 输出最大满意度
print(max_satisfaction(n, items))

发表于 2024-10-31 18:29:58 回复(0)
Python3
神奇的大白菜在记录秋招头像 神奇的大白菜在记录秋招
while 1:
    try:
        pass
        money, m = list(map(int, input().split()))
        money = money // 10
        goods = []
        ma=0
        goods=[[[0]*4] for j in range(m)]
        for i in range(m):
            goods[i][0]=(list(map(int, input().split())))
            goods[i][0][0] = goods[i][0][0] // 10
            goods[i][0][1]=goods[i][0][1]*goods[i][0][0]
        for good in goods:
            if good[0][2]!=0:
                if len(goods[good[0][2]-1])<3:
                    goods[good[0][2]-1].append([good[0][0]+goods[good[0][2]-1][0][0],good[0][1]+goods[good[0][2]-1][0][1],0])
                if len(goods[good[0][2]-1])==3:
                    goods[good[0][2]-1].append([good[0][0]+goods[good[0][2]-1][1][0],good[0][1]+goods[good[0][2]-1][1][1],0])

        dp=[[0]*(money+1) for i in range(m+1)]
        for i in range(1,m+1):
            for j in range(1,money+1):
                for good in goods[i-1]:
                    if good[-1]==0 and good[0]<=j:
                        dp[i][j]=max(dp[i-1][j-good[0]]+good[1],dp[i-1][j],dp[i][j])
                    else:
                        dp[i][j]=max(dp[i-1][j],dp[i][j])
                    ma=max(ma,dp[i][j])
        print(ma*10)
    except:
        break
发表于 2024-09-03 21:15:33 回复(1)
Python3
黝黑的鲁道夫头像 黝黑的鲁道夫 
from collections import defaultdict

def max_satisfaction(n, m, items):
    n //= 10  # 将预算缩小为 10 的倍数
    dp = [0] * (n + 1)
    
    main_items = {}
    attachments = defaultdict(list)

    # 预处理：分类主件和附件
    for i in range(m):
        v, p, q = items[i]
        v //= 10  # 将价格缩小为 10 的倍数
        if q == 0:
            main_items[i + 1] = (v, v * p)  # 记录主件
        else:
            attachments[q].append((v, v * p))  # 将附件附加到主件上

    # 动态规划处理每个主件及其附件的组合
    for key, (base_v, base_w) in main_items.items():
        # 分离处理不同类型的组合
        combinations = [(base_v, base_w)]  # 仅主件
        
        # 考虑附件组合
        if key in attachments:
            attach = attachments[key]
            if len(attach) == 1:
                v1, w1 = attach[0]
                combinations.append((base_v + v1, base_w + w1))  # 主件 + 附件1
            elif len(attach) == 2:
                v1, w1 = attach[0]
                v2, w2 = attach[1]
                combinations.append((base_v + v1, base_w + w1))  # 主件 + 附件1
                combinations.append((base_v + v2, base_w + w2))  # 主件 + 附件2
                combinations.append((base_v + v1 + v2, base_w + w1 + w2))  # 主件 + 附件1 + 附件2
        
        # 使用副本进行更新，防止重复使用
        new_dp = dp[:]
        for c_v, c_w in combinations:
            for j in range(n, c_v - 1, -1):
                new_dp[j] = max(new_dp[j], dp[j - c_v] + c_w)
        dp = new_dp  # 更新dp

    return dp[n] * 10  # 恢复原始预算单位

# 输入处理
n, m = map(int, input().split())
items = [tuple(map(int, input().split())) for _ in range(m)]

# 计算最大满意度
print(max_satisfaction(n, m, items))

发表于 2024-08-14 15:12:49 回复(0)
Python3
_Mukuro头像 _Mukuro
这个示例二中明明第三行，重要度为3的10块物品更好，为什么选择重要度为1的计算
发表于 2024-07-18 11:16:31 回复(5)
Python3
素_14头像 素_14 
有一个用例过不去，好难受啊..........
import sys
import math 
def fun1(s):#计算物品最大公约数
    y = [s[i][0] for i in range(1,len(s))]
    g = y[0]
    for i in range(1,len(y)):
        g = math.gcd(g,y[i])
    return g
   
while True:
    try:

        n = list(map(int,input().split())) 
        m,mm= [[0]],[[0]]
        x,s= [],[]
        d = {}
        t,q = 0,0
        for k in range(1,n[1]+1):
            s = list(map(int,input().split()))            
            s[1] = s[1]*s[0]            
            if s[2] == 0:
                d[k] = [s]
                s[2] = k
                mm.append(s)  #mm存放主件
                
            else:
                m.append(s)  #m存放附件
        
        q = fun1(mm)
        N = n[0]//q + 1
        M =  len(mm)
        # print(m,mm,sep = '\n')
        x = [[0 for i in range(N)] for j in range(M)]
        for i in range(1,len(m)):     #建立主件字典 
            t = m[i][2]
            m[i][0] += d[t][0][0]
            m[i][1] += d[t][0][1]
            if m[i][0] <= n[0]:
                d[t].append(m[i])
            if len(d[t]) == 3:
                s = [d[t][1][0] + d[t][2][0]-d[t][0][0],d[t][1][1] + d[t][2][1]-d[t][0][1] ,t]
                d[t].append(s)
        # print(d)      
        for i in range(1,M):
            t = mm[i][2]
            for j in range(1,N):
                a = x[i-1][j]
                for k in range(len(d[t])):
                    if d[t][k][0] <= j*q:                                               
                        a = max(a,d[t][k][1]+ x[i-1][j-(d[t][k][0]//q)])
                x[i][j] = a
        # if x[M-1][N-1] == 16800:
        #     x[M-1][N-1] = 16700

        print(x[M-1][N-1])
    except:
        break

发表于 2024-05-29 02:55:16 回复(0)
Python3
兔纸_兔纸纸头像 兔纸_兔纸纸
只通过了80%用例，其他用例超时了，欢迎分享进一步剪枝方法。
def find_max(total_money, num, vs, ps, qs):
    max_v = 0
    selected_o = []
    def f(i, money, temp_v):
        nonlocal max_v
        if i == num or len(selected_o) == num:
            if temp_v > max_v:
                max_v = temp_v
            return
        else:
            # i is already selected
            if i in selected_o:
                f(i+1, money, temp_v)
            # i is not selected
            else:
                # i is main
                if qs[i] == 0:
                    if money >= vs[i]:
                        # select i
                        selected_o.append(i)
                        f(i+1, money-vs[i], temp_v+vs[i]*ps[i])
                        selected_o.pop()
                        # not select i
                        f(i+1, money, temp_v)
                    else:
                        f(i+1, money, temp_v)
                # i is not main
                else:
                    i_main = qs[i]-1
                    # i's main is selected
                    if i_main in selected_o:
                        if money >= vs[i]:
                            # select i
                            selected_o.append(i)
                            f(i+1, money-vs[i], temp_v+vs[i]*ps[i])
                            selected_o.pop()
                            # not select i
                            f(i+1, money, temp_v)
                        else:
                            f(i+1, money, temp_v)
                    # i's main is not selected
                    else:
                        if money >= vs[i] + vs[i_main]:
                            # select i and i's main
                            selected_o.append(i)
                            selected_o.append(i_main)
                            f(i+1, money-vs[i]-vs[i_main], temp_v+vs[i]*ps[i]+vs[i_main]*ps[i_main])
                            selected_o.pop()
                            selected_o.pop()
                            # not select i
                            f(i+1, money, temp_v)
                        else:
                            f(i+1, money, temp_v)
    f(0, total_money, 0)
    print(max_v)

while True:
    try:
        total_money, num = list(map(int, input().split()))
        vs = []
        ps = []
        qs = []
        for i in range(num):
            v, p, q = list(map(int, input().split()))
            vs.append(v)
            ps.append(p)
            qs.append(q)
        find_max(total_money, num, vs, ps, qs)
    except:
        break

发表于 2024-04-26 12:35:34 回复(0)
Python3
通信小子头像 通信小子 
n, m = map(int, input().split())
sum=n
price=[[0]*3 for _ in range(m)]
man=[[0]*3 for _ in range(m)]
fu=[0]*m
flag=0
for i in range(m):
    a,b,c = map(int, input().split())
    fu[i]=c
    if c==0:
        flag+=1
        price[i][0]=a
        man[i][0]=a*b
    elif price[c-1][1]==0:
        price[c-1][1]=a
        man[c-1][1]=a*b
    else:
        price[c-1][2]=a
        man[c-1][2]=a*b
a1=int(n/10)+1
matr=[[0]*a1 for _ in range(flag+1)]
cor=0
for i in range(m):
    if fu[i]==0:
        cor+=1
        for k in range(a1):
            if k*10>=price[i][0]:
                matr[cor][k]=max(man[i][0]+matr[cor-1][k-price[i][0]//10],matr[cor-1][k])
                if k*10>=price[i][0]+price[i][1]:
                    matr[cor][k]=max(matr[cor][k],man[i][0]+man[i][1]+matr[cor-1][k-price[i][0]//10-price[i][1]//10],matr[cor-1][k])
                if k*10>=price[i][0]+price[i][2]:
                    matr[cor][k]=max(matr[cor][k],man[i][0]+man[i][2]+matr[cor-1][k-price[i][0]//10-price[i][2]//10],matr[cor-1][k])
                    if k*10>=price[i][0]+price[i][2]+price[i][1]:
                        matr[cor][k]=max(matr[cor][k],man[i][0]+man[i][2]+man[i][1]+matr[cor-1][k-price[i][0]//10-price[i][2]//10-price[i][1]//10],matr[cor-1][k])
            else:
                matr[cor][k]=matr[cor-1][k]
print(matr[flag][a1-1])

发表于 2024-03-22 21:26:31 回复(0)
Python3
慕羽MIN头像 慕羽MIN
简化了一下数据表 
import sys
min_value = 10   # 这个主要简化数据量的大小
n, m = map(int, input().strip().split(' '))

# 主健列表，对应物品的价值 = 价格*重要性
v_list = [0 for i in range(m)]
w_list = [0 for i in range(m)]
# 附件列表
v1_list = {}
w1_list = {}

# 初始化
for i in range(m):
    v, p, q = map(int, input().strip().split(' '))
    if q == 0:
        # v_list.append(int(v // 10))
        # w_list.append(v * p)
        v_list[i] = int(v // min_value)
        w_list[i] = v * p
    else:
        if q-1 in w1_list:
            v1_list[q-1][1] = int(v // min_value)
            w1_list[q-1][1] = v * p
        else:
            v1_list[q-1] = [int(v // min_value), 0]
            w1_list[q-1] = [v * p, 0]

# print('主',v_list,w_list)
# print('主1',v1_list,w1_list)
# 这里开始循环遍历了

# col_num = 0
# 小于10啥也买不了，所有就不去列举了
col_num = int(n / min_value)  
dp = [[0 for i in range(col_num+1)], [0 for i in range(col_num+1)]]
# print(dp)
# dp 初始化
# 初始化
for j in range(col_num+1):
    # 如果金额大于第一件商品的金额
    if j >= v_list[0]:
        dp[0][j] = w_list[0]

    # 如果第一件商品存在附件需要判断其他情况了。
    if 0 in v1_list:

        if j >= v_list[0] + v1_list[0][0]:
            dp[0][j] = max(dp[0][j], w_list[0] + w1_list[0][0])

        if j >= v_list[0] + v1_list[0][1]:
            dp[0][j] = max(dp[0][j], w_list[0] + w1_list[0][1])


        if j >= v_list[0] + v1_list[0][0] + v1_list[0][1]:
            dp[0][j] = max(dp[0][j], w_list[0] + w1_list[0][0] + w1_list[0][1])


# 处理剩余元素
for i in range(1, len(v_list)):
    for j in range(col_num+1):
        # 不选
        x = dp[(i - 1) & 1][j]
        # 选
        if j >= v_list[i]:
            y = dp[(i - 1) & 1][j - v_list[i]] + w_list[i]
        else:
            y = 0

        if i in v1_list:
            if j >= v_list[i] + v1_list[i][0]:
                y = max(y, dp[(i - 1) & 1][j - v_list[i] - v1_list[i][0]] + w_list[i] + w1_list[i][0])

            if j >= v_list[i] + v1_list[i][1]:
                y = max(y, dp[(i - 1) & 1][j - v_list[i] - v1_list[i][1]] + w_list[i] + w1_list[i][1])

            if j >= v_list[i] + v1_list[i][0] + v1_list[i][1]:
                y = max(y, dp[(i - 1) & 1][j - v_list[i] - v1_list[i][0] - v1_list[i][1]] + w_list[i] + w1_list[i][0] + w1_list[i][1])
        # 取两者中的最大值
        dp[i & 1][j] = max(x, y)
        # print(dp)

# print(dp,(len(v_list) - 1),(len(v_list) - 1) & 1,col_num,dp[0])
print(dp[(len(v_list) - 1) & 1][col_num])

编辑于 2024-03-14 19:59:18 回复(0)
Python3
牛客739111788号头像 牛客739111788号 
import sys

line = [i.strip('\n').split() for i in sys.stdin.readlines()]
all_money, buy_num = line[0]

d = [[0 for j in range(0, int(all_money)+1)] for i in range(len(line))]

'''将主件与附件一一对应'''
k = {}
for index,i in enumerate(line):
    if len(i) > 2 and i[-1] != "0":
        if int(i[-1]) not in k.keys():
            k[int(i[-1])] = {}
        if k[int(i[-1])]:
            k[int(i[-1])]["附件2"] = i[:2]
        else:
            k[int(i[-1])]["附件1"] = i[:2]

for i in range(1, len(line)):
    for j in range(10, len(d[0]), 10):
        # if i >=4:
        #     print(i, j)
        if line[i][-1] != "0":
            d[i][j] = d[i-1][j]
        elif i in k.keys():
            if len(k[i]) == 2:
                
                d[i][j] = max(d[i-1][j], # 不选该主件
                d[i-1][j-int(line[i][0])] + int(line[i][0]) * int(line[i][1]) if j-int(line[i][0]) >=0 else 0, # 只选一个主件
                d[i-1][j-int(line[i][0]) - int(k[i]["附件1"][0])] + int(line[i][0]) * int(line[i][1]) +int(k[i]["附件1"][0]) * int(k[i]["附件1"][1])  if j-int(line[i][0])- int(k[i]["附件1"][0]) >=0 else 0,# 选一个主件一个附件1
                d[i-1][j-int(line[i][0]) - int(k[i]["附件2"][0])] + int(line[i][0]) * int(line[i][1]) +int(k[i]["附件2"][0]) * int(k[i]["附件2"][1])  if j-int(line[i][0])- int(k[i]["附件2"][0]) >=0 else 0,# 选一个主件一个附件2
                d[i-1][j-int(line[i][0]) - int(k[i]["附件1"][0])-int(k[i]["附件2"][0])] + int(line[i][0]) * int(line[i][1])+int(k[i]["附件1"][0]) * int(k[i]["附件1"][1])+int(k[i]["附件2"][0]) * int(k[i]["附件2"][1]) if j-int(line[i][0])- int(k[i]["附件1"][0]) -int(k[i]["附件2"][0]) >=0 else 0,# 选一个主件两个附件
                )
            else:
                d[i][j] = max(d[i-1][j], # 不选该主件
                d[i-1][j-int(line[i][0])] + int(line[i][0]) * int(line[i][1]) if j-int(line[i][0]) >=0 else 0, # 只选一个主件
                d[i-1][j-int(line[i][0]) - int(k[i]["附件1"][0])] + int(line[i][0]) * int(line[i][1]) +int(k[i]["附件1"][0]) * int(k[i]["附件1"][1])  if j-int(line[i][0])- int(k[i]["附件1"][0]) >=0 else 0)# 选一个主件一个附件1
        else: # 说明该主件没有附件
            d[i][j] = max(d[i-1][j], # 不选该主件
                d[i-1][j-int(line[i][0])] + int(line[i][0]) * int(line[i][1]) if j-int(line[i][0]) >=0 else 0) # 只选一个主件
        
        
print(d[-1][-1])

编辑于 2024-03-13 11:27:38 回复(0)
Python3
远山有朵云头像 远山有朵云
谢谢大佬，提交通过了，不过重点地方的迭代优化为什么可以这么写还是不太明白惹 
while True:
    try:
        total, N = map(int, input().split())  #将传⼊的函数变量 func 作⽤到 lst 变量的每个元素中
        total = total // 10
        items = {}  #定义字典存储数据
        item_acc = {}
        for i in range(N):
            price, weight, indx = map(int, input().split()) 
            price = price // 10
            if indx == 0:
                items[i+1] = [[price,weight*price]]
            else:
                item_acc[i+1] =[[indx,price,weight]]

        for key in item_acc:
            for indx,price, weight in item_acc[key]:
                new = [[item[0] + price, item[1] + price * weight] for item in items[indx]]
                items[indx].extend(new)

        dp = [0] * (total + 1)
        # print(items)
        for key in items:
            for j in range(total, 0,-1):
                for price, weight in items[key]:
                    if price <= j <= total:
                        dp[j] = max(weight + dp[j - price], dp[j])
        print(10 * max(dp))
    except:
        break


编辑于 2024-02-29 14:23:02 回复(0)
Python3
南边有座山头像 南边有座山 
import math

# 接收输入信息
n_m_list = str(input()).split(" ")
n = int(n_m_list[0])
m = int(n_m_list[1])

v_p_q_list = []
for i in range(m):
    v_p_q_list.append([int(v_p_q) for v_p_q in str(input()).split(" ")])
# 新建存储结构, 用于将主件和附件统一起来
# {q: {'principal': (v, p), 'annex': [(v, p), (v, p)]}, ...}
principal_annex_dict = dict()
# 增加排序, 以确保主件在前

for i, v_p_q in enumerate(v_p_q_list):
    i = i + 1
    v, p, q = v_p_q
    if q == 0:
        if i in principal_annex_dict:
            principal_annex_dict[i]["principal"] = (v, p)
        else:
            principal_annex_dict[i] = dict(principal=(v, p), annex=[])
    else:
        if q in principal_annex_dict:
            principal_annex_dict[q]["annex"].append((v, p))
        else:
            principal_annex_dict[q] = dict(principal=None, annex=[(v, p)])
# 主要部件数量
key_list = [key for key in principal_annex_dict]
key_list.sort(key=lambda x: len(principal_annex_dict[x]['annex']))
principal_len = len(principal_annex_dict)
price_len = math.floor(n / 10) + 1
matrix = [[0 for _ in range(price_len)] for _ in range(principal_len + 1)]


def get_weight(price_now, price, line, weight_now):
    if price_now - price * 10 > 0:
        return matrix[line - 1][price]
    else:
        # 说明可以买, 需要分情况看怎么买
        num_up = matrix[line - 1][price]
        num_now = matrix[line - 1][price - int(price_now / 10)] + weight_now
        return max(num_up, num_now)


for price in range(1, price_len):
    for i, key in enumerate(key_list):
        line = i + 1
        # 判断当前价格是否大于金额, 小于则不能购买, 最优解等于上一行价格
        v, p = principal_annex_dict[key]["principal"]
        annex = principal_annex_dict[key]["annex"]
        temp_list = []
        price_now = v
        weight_now = v * p
        temp_list.append(get_weight(price_now, price, line, weight_now))
        # 增加附件的判断, 分三种情况, 主副1, 主副2, 主副1副2
        if len(annex) >= 1:
            # 主副1
            v_annex, p_annex = annex[0]
            price_now = v + v_annex
            weight_now = v * p + v_annex * p_annex
            temp_list.append(get_weight(price_now, price, line, weight_now))

        if len(annex) == 2:
            # 主副2
            v_annex, p_annex = annex[1]
            price_now = v + v_annex
            weight_now = v * p + v_annex * p_annex
            temp_list.append(get_weight(price_now, price, line, weight_now))
            # 主副1副2
            v_annex_1, p_annex_1 = annex[0]
            v_annex_2, p_annex_2 = annex[1]
            price_now = v + v_annex_1 + v_annex_2
            weight_now = v * p + v_annex_1 * p_annex_1 + v_annex_2 * p_annex_2
            temp_list.append(get_weight(price_now, price, line, weight_now))

        matrix[line][price] = max(temp_list)
# 打印输出数据
print(matrix[principal_len][price_len - 1])

编辑于 2024-02-28 19:07:15 回复(0)
Python3
joey_lu头像 joey_lu 
#贡献一个不用字典纯用列表的做法
tmp = input().split()
money = int(tmp[0])
m = int(tmp[-1])
flag = 10
a=[]
b= []
z = 1
#将主件和附件存为两个双重列表a,b，主件列表的最后增加序号元素用以识别附件
for i in range (m):
    s = input().split()
    for j in range(3):
        s[j] = int(s[j])
    if s[2] == 0:      
        a.append(s)   #是主件的话存a
        a[-1] = a[-1] + [z]
        z += 1
    else:
        b.append(s)   #是附件的话存b
        z += 1        #不管是别到的是主件还是附件序号都要加1
for i in range(len(b)):#将附件存在对应序号的主件
    for j in range(len(a)):
        if b[i][2] == a[j][-1]:#主件列表最后的序号元素匹配附件列表第三个元素（最后一个）
            a[j] = a[j] + b[i]#对应主件的附件增加到主件列表
for j in range(len(a)):
    a[j].pop(3)       #去除序号元素以便后续处理每个主件列表
d=[]
def gaibian(list:list):#参数为每个主件列表，因为每个附件必须先买主件，因此将同一主的所有主附可能性生成为新的列表d
    moneytmp = 0
    satisfy = 0
    c= []
    moneytmp = list[0]
    if moneytmp <= money:#主件是否符合money要求
        satisfy = list[0]*list[1]
        c = c + [moneytmp,satisfy]
    for j in range(3,len(list),3):#主件和附件有多少符合要求的组合，这里写的好像有问题将就着看吧
        moneytmp = moneytmp + list[j]
        if moneytmp <= money:
            satisfy = satisfy + list[j]*list[j+1]
            c = c + [moneytmp,satisfy]#将所有主附搭配的money和满意度重新赋值给新的列表
    if(c != []):         #光是主件就不符合的情况直接排除
        d.append(c)
for i in range(len(a)):
    gaibian(a[i])        #将所有主件列表进行生成新的双重列表d，d的含义为每个主件种类，对应的所有money符合要求的主附组合（money，满意度）
def diedai(list):        #
    c = []
    moneytmp = 0
    satisfy = 0
    if len(list)==1:
        return list      #迭代退出条件
    else:
        for i in range(0,len(list[0]),2):
            for j in range(0,len(list[1]),2): #每次迭代使得两个不同主件对应的（money，满意度）组合合成在一个列表中
                moneytmp =  list[0][i] + list[1][j]  
                if moneytmp <= money:
                    satisfy = list[0][i+1]+list[1][j+1]
                    c= c+[moneytmp,satisfy]   #俩主件的组合由 每一个主件的任一主附组合和另一个主件的任一主附组合加起来组成的新的组合，且满足money要求
        c = c+list[0]+list[1]                 #再加上两个主件自己的任一主附组合等于两个主件所有可能的满足money要求的组合
        list.pop(0)                          #使用完就可以pop掉单一主件的所有可能性
        list.pop(0)
        list.insert(0,c)                     #增添新的组合
        return diedai(list)                  #迭代即参数变化后用同样的逻辑处理
e = diedai(d)                   
print(e)
h = max(e[0][i] for i in range(len(e[0])))   #在所有的组合中找到最大值，即为最大满意度
print(h)  

编辑于 2024-02-23 22:01:38 回复(0)
提交观点

问题信息

动态规划
难度：
54条回答 104685浏览

热门推荐

通过挑战的用户

查看代码

相关试题

购物单

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号