HJ16 购物单

本文主要是介绍HJ16 购物单，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目

https://www.nowcoder.com/practice/f9c6f980eeec43ef85be20755ddbeaf4?tpId=37&tags=&title=&difficulty=0&judgeStatus=0&rp=1&sourceUrl=%2Fexam%2Foj%2Fta%3FtpId%3D37

思路

dp[i][j] i是遍历到第i个物件，j是当前可用预算，dp[i][j]为遍历到第i个物件有预算j时的最大满足值。
当遍历到第i个物件，有预算j 时，有以下情况，取以下情况的最大值作为dp[i][j]的值：

1. 不选择物件i
2. 选择物件i
3. 选择物件i和附件1
4. 选择物件i和附件2
5. 选择物件i和附件1和附件2。
   一个五种情况。当物件i是附件的时候，只能是情况1，是主件的话1到5都得过一遍。选之前要算一下选的物件们的价格，看下当下的预算够不够，不够的话也没法选。

代码

python初始化数组如果用列表需要注意行的复制要用for i in range，如果直接用星号乘会是浅拷贝导致修改一个值所有行的对应位置都会改变。

import sysv = None # m+1,3
w = None # m+1, 3
dp = None # m+1,n+1n, m = None, Nonecnt = 0
for line in sys.stdin:a = line.split()if len(a)==2:n, m = int(a[0])//10, int(a[1])v = [[0]*3 for i in range(m+1)]w = [[0]*3 for i in range(m+1)]dp = [[0]*(n+1) for i in range(m+1)]else:cnt += 1vv, p, q = int(a[0])//10, int(a[1]), int(a[2])if q==0:v[cnt][0] = vvw[cnt][0] = vv*pelse:if v[q][1]:v[q][2] = vvw[q][2] = vv*pelse:v[q][1] = vvw[q][1] = vv*pfor i in range(1, m+1):for j in range(1, n+1):dp[i][j] = dp[i-1][j] # 情况1if v[i][0] <= j: # 情况2dp[i][j] = max(dp[i][j], dp[i-1][j-v[i][0]]+w[i][0])if v[i][0]+v[i][1] <= j: # 3dp[i][j] = max(dp[i][j], dp[i-1][j-v[i][0]-v[i][1]]+w[i][0]+w[i][1])if v[i][0]+v[i][2] <= j: # 4dp[i][j] = max(dp[i][j], dp[i-1][j-v[i][0]-v[i][2]]+w[i][0]+w[i][2])if v[i][0]+v[i][1]+v[i][2] <= j: # 5dp[i][j] = max(dp[i][j], dp[i-1][j-v[i][0]-v[i][1]-v[i][2]]+w[i][0]+w[i][1]+w[i][2])
print(dp[m][n]*10)

Ref

https://blog.csdn.net/weixin_45932570/article/details/115428220

这篇关于HJ16 购物单的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---