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 sys

v = None # m+1,3
w = None # m+1, 3
dp = None # m+1,n+1

n, m = None, None

cnt = 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 += 1
        vv, p, q = int(a[0])//10, int(a[1]), int(a[2])
        if q==0:
            v[cnt][0] = vv
            w[cnt][0] = vv*p
        else:
            if v[q][1]:
                v[q][2] = vv
                w[q][2] = vv*p
            else:
                v[q][1] = vv
                w[q][1] = vv*p

for i in range(1, m+1):
    for j in range(1, n+1):
        dp[i][j] = dp[i-1][j] # 情况1
        if v[i][0] <= j: # 情况2
            dp[i][j] = max(dp[i][j], dp[i-1][j-v[i][0]]+w[i][0])
        if v[i][0]+v[i][1] <= j: # 3
            dp[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: # 4
            dp[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: # 5
            dp[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)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42

Ref

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