首页 > 试题广场 >

购物单

[编程题]购物单

热度指数：484594 时间限制：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}$ 请你帮助王强计算可获得的最大的满意度。

输入描述:

第一行输入两个整数  代表预算、查询到的物品总数。
此后  行，第  行输入三个整数  代表第  件物品的价格、重要度、主件编号。特别地， 代表该物品为主件，否则表示该附件从属于主件 。编号即输入顺序，从  开始。

特别地，保证全部物品的价格  均为  的倍数；且每个主件的附件数不超过  个。

输出描述:

在一行上输出一个整数，代表王强可获得的最大满意度。

示例1

输入

输出

说明

在这个样例中，第三、四、五件物品为主件，第一、二件物品为第五件物品的附件。这就意味着，如果购买了第一件物品或第二件物品，则必须购买第五件物品；但是特别地，如果同时购买了第一件物品和第二件物品，则只需要购买一次第五件物品。
我们可以证明，购买一、二、五件商品，获得的满意度最大，为 。

示例2

输入

输出

备注:

本题已于下方时间节点更新，请注意题解时效性：
1. 2025-05-15 更新题面，新增几组hack数据（暂未进行重测）。
2. 2024-12-13 更新题面。

算法知识视频讲解

Python3

温柔的小哥哥爱健身

小白也是终于搞懂01背包的动态规划了！
# 读取输入并处理空行情况
line = input().strip()
while not line:  # 如果是空行，继续读取下一行
    line = input().strip()
# 从有效行中提取数据
money, m = map(int, line.split())
money //=10
# 生成三个二维数组 重量和满意度乘3用来储存附件的值 附件对应的位置保持为0
weight=[[0]*3 for _ in range(m+1)]
satifaction=[[0]*3 for _ in range(m+1)]
dp=[[0]*(money+1) for _ in range(m+1)]
for i in range(1,m+1):
    price,importance,relation=map(int,input().split())
    price//=10
    # 将输入的价格与满意度加入到weight，satifaction数组，附件的值填写在对应主件

    if relation==0:
        weight[i][0]=price
        satifaction[i][0]=price*importance

    # 如果不是主件，判断对应主件第一个附件位置是否已经赋值，否则将该附件的两个值输入

    elif weight[relation][1]==0:
        weight[relation][1]=price
        satifaction[relation][1]=price*importance
    else:
        weight[relation][2]=price
        satifaction[relation][2]=price*importance

    # 所有商品的价格与重要度已经输入
    # 接下来运用动态规划解决01背包问题
    # 有附件的主件，将每个主件和附件的购买情况都对比一下即可，一共就4种情况。
    # QWQ 说一下我对这个动态规划算法的理解 为什么每一轮都要全部遍历并且记录一遍
    # 是为了在下一轮方便调用 最终目的是为了得到遍历所有商品后的最大值

for i in range(1,m+1):
    # 如果是一维数组 必须严格按照价格逆向遍历 保证物品不重复购买
    # 我们是二维数组 dp值储存而不是实时更新 任意顺序无所谓 反正能直接调用上一轮循环的值
    for j in range(money+1):
        if j >= weight[i][0]:
            dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - weight[i][0]] + satifaction[i][0])
            # 分别对比三种组合与单主件的最优解
            if j >= (weight[i][0] + weight[i][1]):
                dp[i][j]=max(dp[i][j],dp[i-1][j-weight[i][0]-weight[i][1]]+satifaction[i][0]+satifaction[i][1])

            if j >= (weight[i][0] + weight[i][2]):
                dp[i][j] = max(dp[i][j],dp[i-1][j - weight[i][0] - weight[i][2]] +satifaction[i][0] + satifaction[i][2])

            if j >= (weight[i][0] + weight[i][1] + weight[i][2]):
                dp[i][j] = max(dp[i][j],dp[i - 1][j-weight[i][0]-weight[i][1]-weight[i][2]]+
                               satifaction[i][0]+satifaction[i][1]+satifaction[i][2])
        else: # 买不起了就不买
            dp[i][j]=dp[i-1][j]
print(10*dp[i][j])

发表于 2025-09-18 22:53:35 回复(0)

Python3

u1f340

01分组背包问题，难度起码是困难吧

发表于 2025-08-06 14:37:00 回复(0)

Python3

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

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

首先应该明确示例的定义，示例对于理解题目来说非常关键
输入第一行，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

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

这个示例二中明明第三行，重要度为3的10块物品更好，为什么选择重要度为1的计算

发表于 2024-07-18 11:16:31 回复(5)

Python3

素_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()

# 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

简化了一下数据表

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号

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)

提交观点

问题信息

动态规划

难度：

57条回答 13802收藏 106281浏览

通过挑战的用户

查看代码

帅阿衰

2023-01-07 20:08:35
牛客72404...

2022-11-17 21:30:36
Log_x

2022-11-09 14:50:03
zs07

2022-10-21 20:55:30
牛客91897...

2022-10-07 22:52:20

购物单

输入描述:

输出描述:

输入

输出

说明

输入

输出

备注:

问题信息

热门推荐

通过挑战的用户

相关试题