二级域名做网站域名成都网站开发费用

0搬砖 - 蓝桥云课 (lanqiao.cn)
问题描述
这天，小明在搬砖
他一共有n块砖他发现第砖的重量为w价值为i。他突然想从这些砖中选一些出来从下到上堆成一座塔,并且对于塔中的每一块砖来说，它上面所有砖的重量和不能超过它自身的价值。
他想知道这样堆成的塔的总价值(即塔中所有砖块的价值和)最大是多少。
输入格式
输入共n+1行第一行为一个正整数n,表示砖块的数量。后面n行每行两个正整数w,v分别表示每块砖的重量和价值。
输出格式
整数表示答案

python只能通过20%

# //想要堆成更高的塔，应该贪心地将重量较小的砖块放在上面，价值较大的砖块放在下面
# //这样先选择的重量较小的砖，会给后面的堆砌留下更大空间，后选择的价值较大的砖，也更容易堆进塔中
# //对两块砖a(wa，va)，b(wb，vb)，如果 wa <=  & va <= b，无疑a应该放在上面，b应该放在下面
# // 如果重量和价值一大一小，此时有两种情况: wa< wb && va >vb ，或 wa > wb && va< vb
# //假设二者依然有序，b可以放在a下面，但a不可以放在b下面，则有wa <= vb && wb > va，
# // 若wa< wb，联立得wa <= vb< va< wb; 若wa > wb，联立得 vb >= wa > wb > va。
# // 上一行两式均满足va< wb，wa < vb，相加得 va + wa< vb + wb，满足此式时应将b排到后面。# n 的最大值被限制为小于 1000。
# w 的最大值被限制为小于 20。
# v 的最大值被限制为小于 20000。n=int(input())
p=[]
for _ in range(n):w,v=map(int,input().split())p.append({'w':w,'v':v})p.sort(key=lambda x: x['w']+x['v'])
dp=[[0]*(n*20+1) for _ in range(n+1)]for i in range(1,n+1):for j in range(n*20+1):dp[i][j]=dp[i-1][j]  #表示在考虑前 i 个物品时，背包容量为 j 时的最优解等于不选择当前物品（即第 i 个物品），而是继续使用前 i-1 个物品时的最优解for j in range(p[i-1]['v'],-1,-1):  #，从 p[i-1]['v'] 到 0。其中 p[i-1]['v'] 表示第 i 个物品的价值，p[i-1]['w'] 表示第 i 个物品的重量dp[i][j+p[i-1]['w']]=max(dp[i][j+p[i-1]['w']],dp[i-1][j]+p[i-1]['v'])  #j+p[i-1]['w']表示将第 i-1 个物品放入背包后，背包容量增加了 p[i-1]['w']，所能达到的最优解ans=max(dp[n])
print(ans)