| 主件 | 附件 |
| 电脑 | 打印机，扫描仪 |
| 书柜 | 图书 |
| 书桌 | 台灯，文具 |
| 工作椅 | 无 |
输入的第 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 是所属主件的编号）
输出一个正整数，为张强可以获得的最大的满意度。
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
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)
n, m = map(int,input().split()) #给每个输入值强制转换为int型
primary, annex = {}, {}
for i in range(1,m+1): #存当前输入的数据
x, y, z = map(int, input().split())
if z==0:#表示当前输入的数据q是个主件
primary[i] = [x, y]
else:#表示当前输入的数据q是个附件
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)]#开辟背包空间：m(行) * n(列)
w, v= [[]], [[]]
for key in primary: #将当前存好的数据放到w,v两个二维列表中
w_temp, v_temp = [], []
w_temp.append(primary[key][0])#当前往背包里放的物品的主件不带附件
v_temp.append(primary[key][0]*primary[key][1])
if key in annex:#当前往背包里放的物品的主件存在附件
w_temp.append(w_temp[0]+annex[key][0][0])#只带附件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])#只带附件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])#既带附件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的整数倍，步长设为10，动态规划，缩小数据v的数量级
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]) #0-1背包拓展，递归
dp[i][j] = max_i #中间变量归位，供下一趟循环时使用
print(dp[m][n]) #递归调用dp
n, m = input().split()
n, m = int(n), int(m)
l, ln = [], []
d = {}
for i in range(m):
l.append(input().split())
for k, v in enumerate(l):
if v[-1] == "0":
ln.append({'v': int(v[0]), 'p': int(v[1]), 'q': []})
for kj, j in enumerate(l):
if int(j[-1]) == k + 1:
ln[-1]['q'].append({'v': int(j[0]), 'p': int(j[1])})
def r(ls=[], ns=0, ms=0, my=0, mys=0, p=[]):
lc = ls.copy()
for index in range(len(ls)):
i = ls[index]
lc.pop(0)
ns += i['v']
ms += 1
my += i['v'] * i['p']
if ns < n and ms < m:
if 'q' in i and len(i['q']) != 0:
mys = r(i['q'] + lc, ns, ms, my, mys, p)
else:
mys = r(lc, ns, ms, my, mys, p)
mys = my if ns <= n and ms <= m and my > mys else mys
ns -= i['v']
ms -= 1
my -= i['v'] * i['p']
return mys
print(r(ln))
class way:
def __init__(self,money,num) -> None:
self.items = []
self.money = money
self.price=0
self.value=0
self.num = num
def add(self,product):
if product[0] in self.items:
return False
if product[3]==0&nbs***bsp;product[3]-1 in self.items:
a0 = self.price + product[1]
if a0 <=money:
self.items.append(product[0])
self.price=a0
self.value=self.value+product[1]*product[2]
return True
return False
def way_copy(a):
a0 = way(a.money,a.num)
a0.items = a.items.copy()
a0.price = a.price
a0.value = a.value
return a0
def try_add(wayin,products):
way0 = way_copy(wayin)
waymax = way_copy(wayin)
#print(id(way0.items),id(wayin.items))
#print(id(wayin),id(way0),id(waymax))
for i in range(wayin.num):
if wayin.add(products[i]):
if wayin.value>waymax.value:
waymax=way_copy(wayin)
way1=try_add(wayin,products)
if way1.value>waymax.value:
waymax=way_copy(way1)
wayin = way_copy(way0)
return waymax
x = input().split()
money = int(x[0])
m = int(x[1])
products = {}
for i in range(m):
x = input().split()
products[i]=[i,int(x[0]),int(x[1]),int(x[2])]
way0 =way(money,m)
print(try_add(way0,products).value)
5/12组超时，意料之中。没看背包问题说明之前想到的递归，时间复杂度n的n次方了。谁知道说明中的时间复杂度mn是什么意思
重点是附件只有 0个 1个 或者 2个，不会有更多，太坑了，以为会有很多个还得选来选去搜索空间增加太多， 在附件问题上附件数量少直接暴力了
mm, nn = input().split() mm, nn = int(mm), int(nn) maxx = mm//10 spa = [ [0,0,0] for i in range(nn) ] zhujian = [] value = [0 for i in range(maxx+1)] for i in range(nn): a, b, c = input().split() a, b, c = int(a), int(b), int(c) spa[i][0] = a spa[i][1] = b spa[i][2] = c if c == 0 : zhujian.append( i ) for zjnum in zhujian: fjcount = 0 fj = [ [0,0], [0,0] ] for i in range(nn): if spa[i][2] == zjnum+1: # print( fjcount,zjnum) fj[fjcount][0] = spa[i][0] fj[fjcount][1] = spa[i][1] fjcount += 1 low = spa[zjnum][0] // 10 val = spa[zjnum][0]*spa[zjnum][1] if fjcount >= 1: low1 = spa[zjnum][0] // 10 + fj[0][0] // 10 val1 = spa[zjnum][0]*spa[zjnum][1] + fj[0][0]*fj[0][1] if fjcount == 2: low2 = spa[zjnum][0] // 10 + fj[1][0] // 10 val2 = spa[zjnum][0]*spa[zjnum][1] + fj[1][0]*fj[1][1] low3 = spa[zjnum][0] // 10 + fj[0][0] // 10 + fj[1][0] // 10 val3 = spa[zjnum][0]*spa[zjnum][1] + fj[0][0]*fj[0][1] + fj[1][0]*fj[1][1] for j in range(maxx,low-1,-1): value[j] = max( value[j], value[j-low]+val ) if fjcount == 1: if j >= low1 : value[j] = max( value[j], value[j-low1]+val1 ) if fjcount ==2: if j >= low1 : value[j] = max( value[j], value[j-low1]+val1 ) if j >= low2 : value[j] = max( value[j], value[j-low2]+val2 ) if j >= low3 : value[j] = max( value[j], value[j-low3]+val3 ) print(value[maxx])
import sys l1=[] l2=[] l3=[] for line in sys.stdin: a = line.split() l1.append(int(a[0])) l2.append(int(a[1])) if len(a) == 3: l3.append(int(a[2])); # l4=l1[1:] # l5=l2[1:] # for k in range(len(l4)): # dit1[k] = int(l4[k]); # dit2[k] = int(l5[k]); # dit3[k] = int(l3[k]); # if dit3[k] >=1: # dit1[k]+=dit1[dit3[k]] for i in range(len(l3)): if l3[i]>0: l1[i+1]+=l1[l3[i]] l3[i]+=1 # print(l1) # print(l2) # print(l3) # print(l4) money = l1[0] nums = l2[0] datas = l1[1:] datas_num = l3 perfect = l2[1:] # print(money,nums,datas,datas_num) for i in range(len(datas)): for j in range(len(datas)): if datas[i]+datas[j] <= money and datas_num[i]+datas_num[j]<=nums and i<j: print(perfect[i]*datas[i]+perfect[j]*datas[j])
扫描二维码，关注牛客网
下载牛客APP，随时随地刷题
扫一扫，把题目装进口袋
扫描二维码，进入QQ群
扫描二维码，关注牛客公众号
京公网安备
11010502036488号
