| 主件 | 附件 |
| 电脑 | 打印机，扫描仪 |
| 书柜 | 图书 |
| 书桌 | 台灯，文具 |
| 工作椅 | 无 |
输入的第 1 行，为两个正整数N，m，用一个空格隔开。其中 N 表示总钱数， m 为可购买的物品的个数。
从第 2 行到第 m+1 行，第 j 行给出了编号为 j-1 的物品的基本数据，每行有 3 个非负整数 v、p、q。
其中 v 表示该物品的价格，p 表示该物品的重要度，q 表示该物品是主件还是附件。
如果 q=0，表示该物品为主件，如果q>0，表示该物品为附件， q 是所属主件的编号。
数据范围：N<32000，m<60，v<10000，1<=p<=5。
输出一个正整数，为张强可以获得的最大的满意度。
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
由第1行可知总钱数N为50以及希望购买的物品个数m为5； 第2和第3行的q为5，说明它们都是编号为5的物品的附件； 第4~6行的q都为0，说明它们都是主件，它们的编号依次为3~5； 所以物品的价格与重要度乘积的总和的最大值为10*1+20*3+20*3=130
首先应该明确示例的定义，示例对于理解题目来说非常关键
输入第一行，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]) 
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))
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))
有一个用例过不去，好难受啊..........
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
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])
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])
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]) 
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 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])
#贡献一个不用字典纯用列表的做法 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)
扫描二维码，关注牛客网
下载牛客APP，随时随地刷题
扫一扫，把题目装进口袋
扫描二维码，进入QQ群
扫描二维码，关注牛客公众号
京公网安备
11010502036488号
