首页 > 试题广场 >

购物单

[编程题]购物单

热度指数：476425 时间限制：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 更新题面。

算法知识视频讲解

Python

风风风叶

一开始以为附件会紧跟在主件后面，写完的代码只能通过2个例子。

仔细研究了报错的例子以后，q的值不为零时表示附件所属的主件是m个输入值的第q个，基于这个发现，我将所有可能的情况列出只能通过6个例子，报错是说占空间太大了。

参考别人的答案以后，不再列出所有情况。

先创造一个字典，将主件编号作为key，每个主件所有情况对应的[价格，权重]放入value。再初始化一个列表，以总价的值为索引，对应总价的权重为值，然后一个主件一个主件来迭代。

这个程序的优点是附件不限于两个，缺点是不能输出到底买了啥。不过整了快两天，到底买了什么，我就懒得去纠结了。

N, m = map(int, input().split(' '))  # 输入了N 和 m
N = N // 10
# 限定第一行输入的钱数和件数
if N < 3200 and m < 60:
    p1 = {}
    attach=[]
    for item in range(m):
        # 存储m个vpq,价格、重要程度和附件属性
        price, weight, indx = map(int, input().split(' '))
        price = price // 10
        # 这是主件吗？是的话
        if not indx:
            # 买，创造一个key为主件位置的键值对
            p1[item + 1] = [[price, price * weight]]
        else:
            # 为防止附件在主件之前，先将附件数据存储下来。
            attach.append([price, price * weight, indx])
    for j in range(len(attach)):
        if attach[j][2] != 0:    # 如果是附件，attach[j][2]表示所属主件
            l = len(p1[attach[j][2]])
            new = [[attach[j][0] + p1[attach[j][2]][i][0], attach[j][1] + p1[attach[j][2]][i][1]] for i in range(l)]
            p1[attach[j][2]].extend(new)
    # 这样，p1里每个键值对存储了key主件下，只买主件、主件+附件1、主件+附件2、主件+附件1+附件2 这几种情况，[价格，权重]。
    # 现在我不遍历所有情况，而是以价格为索引，权重为value创造一个列表，
    vls = [0] * (N + 1)
    for item in p1:
        for ky in range(N, 0, -1):
            for price, weight in p1[item]:
                if N >= ky >= price:
                    vls[ky] = max(vls[ky - price] + weight, vls[ky])
    print(10 * max(vls))

编辑于 2021-09-19 16:42:27 回复(0)

Python

紫桓殿下

首先先否定一下很多没有算法只是无脑套用结果的答题者，这样的话这题不如不做浪费自己时间。

我看了各家的回答，其中有很多问题，在某些输入的情况下会出现计算错误。

先说一下这个题的大概步骤，

首先是将数据录入到一个二维数组，记录用户的输入

然后就是遍历计算，同时对遍历计算的结果进行保存，每一个物品会使用遍历计算结果新的一行，这一行的结果是对比新加入的物品和上一行历史最佳的对比出来的最好结果。

其中比较容易陷入思维误区的问题就是：

当算到某一个物品的时候，这个物品加上附件物品算出来的结果，一定会大于只有一个物品的结果吗？

答案是否定的。

我们普遍的思路是1+1>1但是这里遇到的情况是未必，因为选择一个物品的结果，会使得剩余的金额减少，减少的金额如果刚好能购买一个非常划算的物品，这个物品的价值足以超过新加的附件的话，这种情况是很有可能的。所以在设计条件语句的时候，不要用思维定式去想当然的认为必然会大于。

我的案例，通过率100%。希望大家能提出改进的想法。

money, things = map(int, input().split())
money = money // 10  # money都是10的整数，整除后，减小循环次数
# 三列分别表示主件，附件1，附件2
weight = [[0] * 3 for _ in range(0, things + 1)]  # 价格
value = [[0] * 3 for _ in range(0, things + 1)]  # 价值=价格*重要度
result = [[0] * (money + 1) for _ in range(0, things + 1)]
for i in range(1, things + 1):
    prices, degree, depend = map(int, input().split())  # 分别为价格，重要性，主附件
    prices = prices // 10

    if depend == 0:  # 主件
        weight[i][0] = prices
        value[i][0] = prices * degree

    elif weight[depend][1] == 0:  # 附件
        weight[depend][1] = prices  # 第一个附件
        value[depend][1] = prices * degree

    else:
        weight[depend][2] = prices  # 第二个附件
        value[depend][2] = prices * degree
# 遍历计算
for i in range(1, things + 1):  # 每几件物品
    for j in range(money, -1, -1):
        if j >= weight[i][0]:  # 当前价格j可以容下第i个主件时,比较（上一个物品对应价格的价值）与（第i个物品的价值 + 余额价格对应上个物品价值）
            result[i][j] = max(result[i - 1][j], result[i - 1][j - weight[i][0]] + value[i][0])
            # 在确定主件可容纳，并做相应计算之后,判断附件的容纳情况，如果主件都没有办法容纳，则附件必定不可容纳
            if j >= (weight[i][0] + weight[i][1]):
                # 当可以容下第i个主件和此主件的第1个附件时，此时需要在比大小时加入当前最优，保证添加附件的结果不会反而更小
                # 比较（当前价格对应上一物品的价值）与（主键价值+附件1价值+上一物品在价格（j-主键价格-附件1价格）时对应的价值）
                result[i][j] = max(result[i][j], result[i - 1][j], result[i - 1][j - weight[i][0] - weight[i][1]] + value[i][0] + value[i][1])

            if j >= (weight[i][0] + weight[i][2]):
                # 可以容下第i个主件和此主件的第2个附件，此时也需要在比大小时加入当前最优，保证添加附件的结果不会反而更小
                # 比较（当前价格对应上一物品的价值）与（主键价值+附件2价值+上一物品在价格（j-主键价格-附件2价格）时对应的价值）,
                result[i][j] = max(result[i][j], result[i - 1][j], result[i - 1][j - weight[i][0] - weight[i][2]] + value[i][0] + value[i][2])
                # 根据3件物品价格之和必然大于等于2件物品的规则，只有在能容纳主件和附件2时，才有判断全部容纳可能性的必要
                if j >= (weight[i][0] + weight[i][1] + weight[i][2]):
                    # 当判断通过，则判断当前值与上物品计算当前价格价值与当前3物品情况价值中最大值，同时还要比较目前最优值
                    result[i][j] = max(result[i][j], result[i - 1][j], result[i - 1][j - weight[i][0] - weight[i][1] - weight[i][2]] + value[i][0] + value[i][1] + value[i][2])
        else:
            # 当前价格j不能容下第i个主件时,价值为上一个物品的对应价格的价值
            result[i][j] = result[i - 1][j]
print(result[things][money] * 10)

编辑于 2021-05-04 15:49:12 回复(15)

Python

catxjd

看通过的代码里Python解法一堆都是这个

if(1500== _n and 7== _m):

print(6200)

continue

if(2000== _n and 10== _m):

print(7430)

continue

if(4500== _n and 12== _m):

print(16700)

continue

if(6000== _n and 15== _m):

print(26400)

continue

if(8000== _n and 20== _m):

print(36400)

continue

if(14000== _n and 25== _m):

print(59350)

continue

if(18000== _n and 30== _m):

print(75800)

continue

if(24000== _n and 40== _m):

print(96000)

continue

if(30000== _n and 50== _m):

print(120800)

continue

if(1000== _n and 5== _m):

print(3900)

continue

看不懂这些值的意义是什么

发表于 2021-04-14 16:38:25 回复(2)

Python

生活不易123

研究了好几天，来发一个简单好懂的Python AC

N,m = map(int,input().split()) #N =money m=item number
N/=10
N=int(N)
values = [[0,0,0] for _ in range(m+1)]
weights = [[0,0,0] for _ in range(m+1)]
f = [[0]*(N+1) for _ in range(m+1)]
for i in range(1,m+1):
    v,p,q = map(int,input().split())
    v/=10
    v= int(v)
    if q == 0: # main 
        values[i][0] = ***bsp;       weights[i][0] = v

    else:
        if weights[q][1] == 0:
            values[q][1] = ***bsp;           weights[q][1] = v
        else:
            values[q][2] = ***bsp;           weights[q][2] = v

for i in range(1,m+1):
    for j in range(N,0,-1):
        temp = [f[i-1][j]]
        if j>=weights[i][0]: # main
            temp.append(max(f[i-1][j] , f[i-1][j-weights[i][0]] + values[i][0]))
        if j>=weights[i][0] +weights[i][1]: # main + annex 1
            temp.append(max(f[i-1][j],  f[i-1][j-weights[i][0]-weights[i][1]] + values[i][0] +  values[i][1]))
        if j>=weights[i][0] +weights[i][1] + weights[i][2]: # main + annex 1 + annex 2
            temp.append(max(f[i-1][j],  f[i-1][j-weights[i][0]-weights[i][1]-weights[i][2]]+values[i][0]+values[i][1]+values[i][2]))
        if j>=weights[i][0] + weights[i][2]: # main + annex 2
            temp.append(max(f[i-1][j],  f[i-1][j-weights[i][0]-weights[i][2]] + values[i][0] +  values[i][2]))
        f[i][j] = max(temp)
print(f[m][N]*10)

编辑于 2021-03-03 13:47:02 回复(2)

Python

牛客777996133号

Python组写的那是啥？？

发表于 2021-02-11 17:06:34 回复(1)

Python

音无弦音

不知道为什么我的python程序一直报超时，但我的时间复杂度只有O(m*n)，n为物品种类，m为最大金额，为什么会超时啊？？？

import sys


txt=input()
money=int(txt[0:txt.find(' ')])
n=int(txt[txt.find(' ')+1:])
v=[]
p=[]
q=[]
fushu=[]
for i in range(n):
    txt=input()
    p1=txt.find(' ')
    p2=txt.find(' ',p1+1)
    v.append(int(txt[0:p1]))
    p.append(int(txt[p1+1:p2]))
    q.append(int(txt[p2+1:])-1)
    fushu.append([])
    if q[i]>=0:
        fushu[q[i]]=fushu[q[i]]+[i]
F=[[0 for i in range(money+1)] for i in range(n)]
for i in range(0,n):
    for j in range(1,money+1):
        if q[i]<0:
            if i==0:
                F[i][j]=F[i][j-1]
            else:
                F[i][j]=max(F[i-1][j],F[i][j-1])
            if j>=v[i]:
                F[i][j]=max(F[i][j],F[i-1][j-v[i]]+v[i]*p[i])
            if len(fushu[i])==1:
                fs=fushu[i][0]
                if j>=v[i]+v[fs]:
                    F[i][j]=max(F[i][j],F[i-1][j-v[i]]+v[i]*p[i],F[i-1][j-v[i]-v[fs]]+v[i]*p[i]+v[fs]*p[fs])
            if len(fushu[i])==2:
                fs1=fushu[i][0]
                fs2=fushu[i][1]
                if j>=v[i]+v[fs1]:
                    F[i][j]=max(F[i][j],F[i-1][j-v[i]-v[fs1]]+v[i]*p[i]+v[fs1]*p[fs1])
                if j>=v[i]+v[fs2]:
                    F[i][j]=max(F[i][j],F[i-1][j-v[i]-v[fs2]]+v[i]*p[i]+v[fs2]*p[fs2])
                if j>=v[i]+v[fs1]+v[fs2]:
                    F[i][j]=max(F[i][j],F[i-1][j-v[i]-v[fs1]-v[fs2]]+v[i]*p[i]+v[fs1]*p[fs1]+v[fs2]*p[fs2])
        else:
            F[i][j]=F[i-1][j]
print(F[n-1][money])

发表于 2021-02-10 02:00:15 回复(1)

Python

牛客857986449号

发一下我的代码，应该是最简单的

while True:
    try:
        total, N = map(int, input().split())
        total = total // 10
        items = {}
        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:
                new = [[item[0] + price, item[1] + price * weight] for item in items[indx]]
                items[indx].extend(new)
        dp = [0] * (total + 1)
        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

首先是数据转换，对于主件与附件，这里使用了一个列表去迭代。例如，

转换为

{1: [[80, 160], [120, 360], [110, 310], [150, 510]],
 4: [[40, 120]],
 5: [[50, 100]]}

键是主件所在的行数，值是主件与附件所有可能的组合。

最后就是迭代更新dp了, 对于每个key，也就是主件与附件的列表，使用最大的一个旧值去更新新值。注意，0-1背包问题里，价格是降序迭代的。

==============================================================

这里有一个假设，主件总是先于它的附件出现的。否则主附件的组合这部分的代码会有逻辑问题。

编辑于 2021-01-31 23:35:51 回复(6)

Python

CBen123

有依赖的背包问题：先转化成组合背包问题，再转化成0-1背包问题

# -*- coding: utf-8 -*-

from itertools import combinations


# 迭代附件
def iter_items(items):
    for i in range(len(items) + 1):
        yield from combinations(items, i)


# 输入多个数字
def input_ints():
    return map(int, input().split())


def main():
    # 物品字典
    items = {}
    # 公约数，用于减少数组长度，题目给了为10
    common_divisor = 10
    capacity, count = input_ints()
    capacity = int(capacity / common_divisor)
    
    for i in range(1, count + 1):
        price, weight, sub_index = input_ints()
        price = int(price / common_divisor)
        weight *= price  # 直接计算价值
        
        if sub_index == 0:
            items[i] = {
                'main': (price, weight),
                'sub': []
            }
        else:
            items[sub_index]['sub'].append((price, weight))

    max_values = [0] * (capacity + 1)
    new_max_values = []

    for item in items.values():
        for i in range(capacity + 1):
            max_value = max_values[i]

            for sub_items in iter_items(item['sub']):
                price, weight = item['main']

                for sub_price, sub_weight in sub_items:
                    price += sub_price
                    weight += sub_weight

                if price > i:
                    continue

                value = max_values[i - price] + weight
                max_value = max(max_value, value)

            new_max_values.append(max_value)

        max_values = new_max_values
        new_max_values = []

    print(max_values[-1] * common_divisor)


if __name__ == '__main__':
    main()

发表于 2021-01-04 19:25:31 回复(0)

Python

大溪地渔民

import sys


def process_data(n):
    goods = [None]
    for s in sys.stdin:
        if not s.split():
            continue
        p, w, i = map(int, s.split())
        p, w = p//10, (p//10)*w
        if not i:
            goods.append([(p, w)])
        else:
            goods[i].append((p, w))
            goods.append(None)
    goods = [_ for _ in goods if _]
    return goods


def do_dp(m, goods):
    m = m//10
    dp = [0] * (m+1)
    for tup in goods:
        tup += [None, None]
        mg, sg1, sg2 = tup[:3]
        mg_p, mg_w = mg
        if sg1:
            sg1_p, sg1_w = sg1
        if sg2:
            sg2_p, sg2_w = sg2
        for i in range(m, 0, -1):
            if mg_p > i:
                break
            dp[i] = max([dp[i], dp[i-mg_p]+mg_w])
            if sg1 and mg_p+sg1_p<=i:
                dp[i] = max([dp[i], dp[i-mg_p-sg1_p]+mg_w+sg1_w])
            if sg2:
                if mg_p+sg2_p<=i:
                    dp[i] = max([dp[i], dp[i-mg_p-sg2_p]+mg_w+sg2_w])
                if mg_p+sg1_p+sg2_p<=i:
                    dp[i] = max([dp[i], dp[i-mg_p-sg1_p-sg2_p]+mg_w+sg1_w+sg2_w])
    return dp[m]*10


m, n = map(int, input().split())
goods = process_data(n)
print(do_dp(m, goods))

发表于 2020-12-21 23:41:29 回复(0)

Python

左路谢桥

n, m = map(int, input().split())  # n为总钱数，m为物品个数
# 分组背包，每组有四种情况，a.主件 b.主件+附件1 c.主件+附件2 d.主件+附件1+附件2
# 就是按条件再生成四个物品，得出每个物品的属性，从四个物品里选一个物品购买
v = [[0 for i in range(4)] for j in range(m + 1)]  # 每组的资金
w = [[0 for i in range(4)] for j in range(m + 1)]  # 每组的重要度*资金

# 生成物品组
for i in range(1, m + 1):
    x, y, z = map(int, input().split())  # v为价格，p重要度，q主键还是附件
    x = x // 10
    if z == 0:  # 得到一个主件，开始生成含这个主件的四个货物
        for l in range(4):  # v[i]初始为[0,0,0,0]
            v[i][l] += x  # 输出[x,x,x,x]第i组的价格
            w[i][l] += x * y
    elif v[z][1] == v[z][0]:  # 附件且a==b，意味着附件1没加入，这时候累加b跟d情况
        v[z][1], w[z][1] = v[z][1] + x, w[z][1] + x * y
        v[z][3], w[z][3] = v[z][3] + x, w[z][3] + x * y
    else:  # 附件且a!=b，意味着附件1加入了附件2没加入
        v[z][2], w[z][2] = v[z][2] + x, w[z][2] + x * y
        v[z][3], w[z][3] = v[z][3] + x, w[z][3] + x * y

# 开始计算最大重要度
n = n // 10
f = [0] * (n+1) # [0,0,0,0,0,0,......]
for i in range(1, m + 1):

    for j in reversed(range(1, n + 1)):
        for l in range(4):
            if v[i][l] <= j:  # 如果组内第l件价格大于j
                f[j] = max(f[j], w[i][l] + f[j - v[i][l]])
print(f[n]*10)

发表于 2020-11-30 16:25:23 回复(0)

Python

自己剃头的童仔

动态规划问题，前面有很多答案，我这里采用一个记录路径的方式解决。优点是有的时候动态规划的题目会同时让你输出具体的过程信息，那么这种方式就很直观，也方便排错。

设dp[n][0]为花了n元钱共获得的总价值，即v1*p1+v2*p2+...；

而dp[n][1]记录被选择的物品编号列表。物品个数最大只有60个，所以此列表并不需要进行优化。若进行优化，则优化方式可以利用二进制位操作记录整数的方式等等。利用python对列表应用的特性，就可以方便的判断某个数是否在列表中，即dp[n][1]是否包含当前的物品编号（或当前物品的q值，即父亲物品编号）。

虽然数组（Python中是列表）是二维，但动态规划其实只是一维动态规划，即完全可以把dp[n][1]单独用另一个数组记录。受益于Python的灵活性，此处用一个可变的列表进行记录操作。

那么对于总价值最优判断就有两个可能性：

1。当前物品的父物品q已经被选择，那么就考虑放入当前物品后，价值是否更大，即(dp[i-v][0]+v*p)>dp[i][0]；

2。当前物品的父物品q没有被选择，那么就考虑两个物品都放入，价值是否更大，即(dp[i-v-parent_v][0]+v*p+q_v*q_p)>dp[i][0]，其中q_v和q_p代表父物品q的价值v和重要度p。当然，前提是当前物品没有被重复放入，且父亲物品q之前也没有被放入。

之所以要进行第二个可能性的考虑，是因为对数组进行遍历修改取优值的时候，必须保证每种物品都可以在不依赖遍历顺序的前提下有选择的放入背包，也就是普通的0-1背包问题。不管你是先从第一个物品开始选，还是最后一个物品，还是中间某个物品，都不会对结果产生影响。

而这里，如果你遍历物品按照输入的顺序，有可能出现子物品先入库，而父物品还没有入库的情形，从而造成此子物品由于父物品还未纳入考虑，而完全不可能被选择的情况。

解决这种有条件性的问题，就是列出可能让他放入的各种条件。这也就是很多人考虑父子物品的时候，干脆都按照同等地位的物品进行考虑，也即父物品单独入库，父+子物品，父+子2物品，父+子3物品，父+子1+子2，父+子2+子3，父+子1+子3。。。这样使每种子物品变成了父+子物品的绑定形态。而题目中限定了子物品的个数为2，所以只需要列举父物品单独选择，父+子1物品，父+子2物品和父+子1+子2这几种可能性。相比之下，我的想法在子物品过多的情况下，会更容易。因为任何一种子物品入库，都可以只去考虑他的父物品，而不再需要考虑他的兄弟物品是否入库的情形。

除此之外，对动态规划永远都用倒序遍历，同时记得判断下标不要越界，没IDE的时候多写几个if判断界限不丢人。

用例100%通过。

while True:
    try:
        total_money,total_num=map(int,input().split(' '))
        total_money//=10
        product_item=[]
        for i in range(total_num):
            v,p,q=map(int,input().split(' '))
            v//=10
            product_item+=[[i+1,v,p,q]]
        dp=[[0,[0]] for i in range(total_money+1)]
 
        for current_no,v,p,q in product_item:
            for i in range(len(dp)-1,-1,-1):
                if (i-v)>=0:
                    if not current_no in dp[i-v][1]:
                        if q in dp[i-v][1]: # the parent has been chosen.
                            if (dp[i-v][0]+v*p)>dp[i][0]:
                                dp[i][0]=dp[i-v][0]+v*p
                                dp[i][1]=dp[i-v][1].copy()
                                dp[i][1]+=[current_no]
                        else: # the parent has not been chosen, then we can pick up both current one and the parent.
                            if (i-v-product_item[q-1][1])>0:
                                if (dp[i-v-product_item[q-1][1]][0]+v*p+product_item[q-1][1]*product_item[q-1][2])>dp[i][0] and not current_no in dp[i-v-product_item[q-1][1]][1] and not q in dp[i-v-product_item[q-1][1]][1]:
                                    dp[i][0]=dp[i-v-product_item[q-1][1]][0]+v*p+product_item[q-1][1]*product_item[q-1][2]
                                    dp[i][1]=dp[i-v-product_item[q-1][1]][1].copy()
                                    dp[i][1]+=[current_no]
                                    dp[i][1]+=[q]
        print(dp[total_money][0]*10)
    except:
        break

编辑于 2020-10-16 14:58:57 回复(0)

Python

Ddz_大傻子

各位大佬们，我不是很理解下面这句话：

“如果 q=0 ，表示该物品为主件，如果 q>0 ，表示该物品为附件， q 是所属主件的编号”

当q>0, q是所属主件的编号是指对应的第n个主件是吗？

发表于 2020-09-12 20:02:36 回复(2)

Python

牛客5936512

import sys
while True:
line = sys.stdin.readline().strip()
if not line:
break
N, m = map(int, line.split())
N//=10
dp = [0]*(N+1)
vv = [0]*m
pp = [0]*m
qq = [0]*m
s = {}
for i in range(m):
v, p, q = map(int, input().split())
vv[i] = v//10
pp[i] = p
qq[i] = q
if q:
if q-1 in s:
s[q-1].append(i)
else:
s[q-1]=[i]
elif i not in s:
s[i] = []
for i in s:
_dp = [0]*(vv[i]-1)+[pp[i]*vv[i]]*(N-vv[i]+2)
for j in s[i]:
for k in range(N, vv[i]+vv[j]-1, -1):
_dp[k] = max(_dp[k-vv[j]]+vv[j]*pp[j], _dp[k])
mx = 0
w=[]
for j in range(vv[i], N+1):
if mx < _dp[j]:
mx = _dp[j]
w.append([j, _dp[j]])
for k in range(N, -1, -1):
__dp = 0
for ww in w:
if ww[0]>k:
continue
__dp = max(__dp, dp[k-ww[0]]+ww[1])
dp[k] = max(__dp, dp[k])
print(dp[N]*10)

发表于 2020-08-27 02:16:02 回复(0)

Python

NOSIGNAL

n,m=map(int,input().split(' '))
pri={}
ann={}
for i in range(1,m+1):
    w_temp,v_temp,flag_=map(int,input().split(' '))
    if flag_==0:
        pri[i]=[w_temp,w_temp*v_temp]
    else:
        if flag_ in ann:
            ann[flag_].append([w_temp,w_temp*v_temp])
        else:
            ann[flag_]=[]
            ann[flag_].append([w_temp, w_temp * v_temp])
w=[[],]
v=[[],]
m=len(pri)
for key in pri:
    w.append([pri[key][0]])
    v.append([pri[key][1]])
    if key in ann.keys():
        w[-1].append(w[-1][0]+ann[key][0][0])
        v[-1].append(v[-1][0] + ann[key][0][1])
        if len(ann[key])>1:
            w[-1].append(w[-1][0] + ann[key][1][0])
            v[-1].append(v[-1][0] + ann[key][1][1])
            w[-1].append(w[-1][1] + w[-1][2]-w[-1][0])
            v[-1].append(v[-1][1] + v[-1][2]-v[-1][0])

dp=[[0]*(n+1) for _ in range(m+1)]
for i in range(1,m+1):
    for j in range(10,n+1,10):
        max_i=dp[i-1][j]
        for k in range(len(w[i])):
            if j>=w[i][k]:
                max_i=max(max_i,dp[i-1][j-w[i][k]]+v[i][k])
        dp[i][j]=max_i
print(dp[m][n])

发表于 2020-08-23 09:53:38 回复(0)

Python

Aaron_c

import sys
N, m = list(map(int,sys.stdin.readline().strip().split()))
input_item, item, result = [], [0], 0
for i in range(m):
    input_item.append(list(map(int,sys.stdin.readline().strip().split())))
def FindNext(input_item, item, N, m, result):
    for i in range(m):
        if input_item[i][2] in item and input_item[i][0] <= N and (i+1) not in item:
            temp = [i for i in item]
            temp.append(i+1)
            result = FindNext(input_item, temp, (N-input_item[i][0]), m, result)
    return max(result,sum([input_item[i-1][0]*input_item[i-1][1] for i in item[1:]]))
result = FindNext(input_item, item, N, m, result)
print(result)

写了个递归函数，思路比较简单，但是会重复遍历相同的组合，导致时间复杂度过高，测试用例长了就会超时

希望能有大佬帮我提供下改进的思路

编辑于 2020-08-21 23:31:54 回复(0)

Python

牛客795725540号

只能通过百分之60  找不到错误在哪，换成一维数组就能AC，有大佬帮忙看看吗
while True: try:
        n, m = map(int, input().split())
        f = [[0] * (n // 10 + 1) for _ in range(m+1)]
        rec = [] for i in range(m):
            num = list(map(int, input().split()))
            rec.append(num)
        v = [[0] * 4 for _ in range(m + 1)]
        w = [[0] * 4 for _ in range(m + 1)] for i in range(0,m): if rec[i][2] == 0: for j in range(4):
                    v[i+1][j] = rec[i][0]
                    w[i+1][j] = rec[i][0] * rec[i][1] elif v[rec[i][2]][0] == v[rec[i][2]][1]:
                v[rec[i][2]][1] += rec[i][0]
                w[rec[i][2]][1] += rec[i][1] * rec[i][0]
                v[rec[i][2]][3] += rec[i][0]
                w[rec[i][2]][3] += rec[i][1] * rec[i][0] else:
                v[rec[i][2]][2] += rec[i][0]
                w[rec[i][2]][2] += rec[i][1] * rec[i][0]
                v[rec[i][2]][3] += rec[i][0]
                w[rec[i][2]][3] += rec[i][1] * rec[i][0] for i in range(1,m+1): for j in range(n // 10 + 1): for k in range(4): if j * 10 >= v[i][k]:
                        f[i][j] = max(f[i-1][j], f[i-1][j - v[i][k]//10] + w[i][k]) else:
                        f[i][j] = f[i-1][j] print(f[m][n // 10]) except: break

发表于 2020-08-20 22:15:33 回复(0)

Python

牛客721370495号

写了一天终于过了

懒得解释，脑阔疼

while True:
    try:
        N, m = map(int, input().split())
        N //= 10
        ls = []
        for i in range(m):
            ls.append(list(map(int, input().split()))+[i+1])
        for i in range(len(ls)):
            ls[i][0] //= 10
        dic = {}
        for item in ls:
            if item[2] == 0:
                dic[item[3]] = [item[:2]]
        for item in ls:
            if item[2]:
                dic[item[2]].append(item[:2])
        items = []
        for item in dic.values():
            cur = []# [钱，权重]组成的列表
            cur.append([item[0][0], item[0][0]*item[0][1]])
            if len(item) > 1:
                cur.append([item[1][0]+item[0][0], item[0][0]*item[0][1]+item[1][0]*item[1][1]])
            if len(item) > 2:
                cur.append([item[2][0]+item[0][0], item[0][0]*item[0][1]+item[2][0]*item[2][1]])
                cur.append([item[2][0]+item[1][0]+item[0][0], item[0][0]*item[0][1]+item[1][0]*item[1][1]+item[2][0]*item[2][1]])
            cur.sort(key=lambda x: x[0])
            items.append(cur)
        dp = [[0]*(N+1) for i in range(len(items))]
        for i in range(len(items)):
            for j in range(N+1):
                for item in items[i]:
                    if item[0] > j:
                        dp[i][j] = max(dp[i][j], dp[i-1][j] if i>0 else 0, dp[i][j-1] if j>0 else 0)
                    else:
                        dp[i][j] = max(item[1]+(dp[i-1][j-item[0]] if i>0 else 0), dp[i][j], dp[i-1][j] if i>0 else 0, dp[i][j-1] if j>0 else 0)
        print(max(dp[-1])*10)
    except:
        break

发表于 2020-07-24 00:54:47 回复(0)

Python

牛客826676341号

解答之前去看了背包九讲，以我自己的思路重新解构成分组背包问题，测试用例全过。python2.7代码

while True:
    try:
        N,m = map(int,raw_input().split())
        f = [0]*(N+1)
        goods = []
        groups = []
        for i in range(m):
            goods.append(map(int,raw_input().split()))
        for i in range(m):
            if goods[i][2] == 0:
                group = []
                group.append(goods[i])
                for j in range(m):
                    if goods[j][2] == i + 1:
                        group.append(goods[j])
                groups.append(group)
        for i in range(len(groups)):
            group = groups[i]
            for j in range(N, group[0][0] - 1,-1):
                for k in range(0, len(group)):
                    if k == 0:
                        f[j] = max(f[j], f[j - group[0][0]] + group[0][0]*group[0][1])
                    else:
                        if j >= group[0][0] + group[k][0]:
                            f[j] = max(f[j], f[j - group[0][0] - group[k][0]] + group[0][0]*group[0][1] + group[k][0] * group[k][1])
                    if k == 2:
                        if j >= group[0][0] + group[1][0] + group[2][0]:
                            f[j] = max(f[j], f[j - group[0][0] - group[1][0] -  group[2][0]] + group[0][0]*group[0][1] + group[1][0] * group[1][1] + group[2][0] * group[2][1])
        print int(f[N])
    except:
        break

发表于 2020-05-25 00:02:16 回复(0)

提交观点

问题信息

动态规划

难度：

37条回答 13479收藏 104692浏览

通过挑战的用户

查看代码

帅阿衰

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

购物单

输入描述:

输出描述:

输入

输出

说明

输入

输出

备注:

问题信息

热门推荐

通过挑战的用户

相关试题