Python礼物问题

期末考试小明取得了优异的成绩，妈妈为鼓励小明再接再厉，在网购平台指定了N（2≤N≤50）件礼物供小明挑选。挑选前妈妈提出了以下要求：

1）每种礼物只能挑选1件；

2）所挑选的礼物总价格不能大于V（1≤V≤100）。

已知N件礼物中每件礼物的价格和小明对每件礼物的喜爱值（喜爱值越大喜爱程度越高），请你帮助小明挑选礼物，使得挑选的所有礼物在满足要求的前提下，总的喜爱值最大，并输出最大喜爱值。

例如：

N = 3，V=5，3件礼物的价格和喜爱值分别为（1，2），（2，4），（3，3）。

可挑选第二件礼物（2，4）和第三件礼物（3，3），总价格为5（5=2+3），总喜爱值为7（7=4+3），总价格不大于5且喜爱值最大，输出7。

img


输入描述
第一行输入两个正整数N（2≤N≤50）和V（1≤V≤100），分别表示指定的礼物数量和所挑选的礼物总价格不能大于的值，正整数之间以一个英文逗号隔开

第二行开始，输入N行，每行输入两个正整数J（1≤J≤V）和K（1≤K≤100），分别表示每件礼物的价格和喜爱值，正整数之间以一个英文逗号隔开

输出描述
输出一个整数，表示在满足题目要求下的最大喜爱值

样例输入
3,5
1,2
2,4
3,3
样例输出
7

求帮助！

该回答引用ChatGPT
该代码使用了动态规划的思想，具体来说，定义状态 $dp_i$ 表示总价格不超过 $i$ 时可以获得的最大喜爱值，状态转移方程为：

$dp_j = max(dp_j, dp_{j-w_i} + v_i)$

其中，$w_i$ 和 $v_i$ 分别表示第 $i$ 件物品的价格和喜爱值。

def findMaxLove(n, v, items):
    dp = [0 for i in range(v + 1)]
    for i in range(n):
        for j in range(v, items[i][0] - 1, -1):
            dp[j] = max(dp[j], dp[j - items[i][0]] + items[i][1])
    return dp[v]

n = 3
v = 5
items = [(1, 2), (2, 4), (3, 3)]
print(findMaxLove(n, v, items))

大哥这是蓝桥杯原题，你是不是作弊了

这道题目涉及到了背包问题，具体来说是0/1背包问题，因为每件物品只能选择一次。

解决这道题目的方法是使用动态规划，具体过程如下：

定义状态：设dp[i][j]表示前i件礼物中挑选价格不大于j时的最大喜爱值
状态转移方程：如果第i件礼物的价格小于等于j，那么dp[i][j]=max(dp[i-1][j],dp[i-1][j-v[i]]+w[i])，否则dp[i][j]=dp[i-1][j]；其中v[i]表礼物i的价格，w[i]表礼物i的喜爱值。
初始状态：dp[0][j]=0，表礼物数量为0时，最大喜爱值为0。
结果：最终答案即为dp[n][v]。

代码如下（python）：

def getMaxValue(n,v,values,weights):
    dp=[[0]*(v+1) for i in range(n+1)]
    for i in range(1,n+1):
        for j in range(1,v+1):
            if j<values[i-1]:
                dp[i][j]=dp[i-1][j]
            else:
                dp[i][j]=max(dp[i-1][j],dp[i-1][j-values[i-1]]+weights[i-1])
    return dp[n][v]

if __name__=="__main__":
    n,v=map(int,input().split(','))
    values=[]
    weights=[]
    for i in range(n):
        value,weight=map(int,input().split(','))
        values.append(value)
        weights.append(weight)
    print(getMaxValue(n,v,values,weights))
不知道你这个问题是否已经解决, 如果还没有解决的话:

如果你已经解决了该问题, 非常希望你能够分享一下解决方案, 写成博客, 将相关链接放在评论区, 以帮助更多的人 ^-^