网站开发与网站运营,中国企业排行榜前十名,可以做免费推广的网站有哪些,赣州网站设计有哪些0搬砖 - 蓝桥云课 (lanqiao.cn) 问题描述 这天#xff0c;小明在搬砖 他一共有n块砖他发现第砖的重量为w价值为i。他突然想从这些砖中选一些出来从下到上堆成一座塔,并且对于塔中的每一块砖来说#xff0c;它上面所有砖的重量和不能超过它自身的价值。 他想知道这样堆成的塔的…0搬砖 - 蓝桥云课 (lanqiao.cn) 问题描述 这天小明在搬砖 他一共有n块砖他发现第砖的重量为w价值为i。他突然想从这些砖中选一些出来从下到上堆成一座塔,并且对于塔中的每一块砖来说它上面所有砖的重量和不能超过它自身的价值。 他想知道这样堆成的塔的总价值(即塔中所有砖块的价值和)最大是多少。 输入格式 输入共n1行第一行为一个正整数n,表示砖块的数量。后面n行每行两个正整数w,v分别表示每块砖的重量和价值。 输出格式 整数表示答案
python只能通过20%
# //想要堆成更高的塔应该贪心地将重量较小的砖块放在上面价值较大的砖块放在下面
# //这样先选择的重量较小的砖会给后面的堆砌留下更大空间后选择的价值较大的砖也更容易堆进塔中
# //对两块砖a(wava)b(wbvb)如果 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 wbwa vb相加得 va wa vb wb满足此式时应将b排到后面。# n 的最大值被限制为小于 1000。
# w 的最大值被限制为小于 20。
# v 的最大值被限制为小于 20000。nint(input())
p[]
for _ in range(n):w,vmap(int,input().split())p.append({w:w,v:v})p.sort(keylambda x: x[w]x[v])
dp[[0]*(n*201) for _ in range(n1)]for i in range(1,n1):for j in range(n*201):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][jp[i-1][w]]max(dp[i][jp[i-1][w]],dp[i-1][j]p[i-1][v]) #jp[i-1][w]表示将第 i-1 个物品放入背包后背包容量增加了 p[i-1][w]所能达到的最优解ansmax(dp[n])
print(ans)
