牛客华为HJ16_购物单

发表于 分类于
这是文章开头，显示在主页面，详情请点击此处。
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
43
44
45
46
47
48
49
50
51
52
53
54
55
import sys # 典型的 01 背包问题，只取一次。
# 制作主副件 数据结构
def build_structure():
    N,m = input().split()
    N,m = int(N)//10,int(m)
    values,utility = [[0 for _ in range(3)] for s in range(0,m+1)],\
    [[0 for _ in range(3)]  for s in range(0,m+1)]
    i = 1
    for line in sys.stdin:
        a = line.split()
        v,p,q = int(a[0])//10,int(a[1]),int(a[2])
        # print(v,p,q)
        if q != 0: # 附件是 跟在 主键后面。 这个存储结构 模仿的描述图片。可以清晰看见主附件结构。
            if values[q][1]==0:  # 附件 1 
                values[q][1] = v
                utility[q][1] = p*v
            else:                   # 附件 2
                values[q][2] = v
                utility[q][2] = p*v
        else:                       # 主件
            values[i][0] = v
            utility[i][0] = p*v
        i += 1
    return values,utility,N,m

# d[i][j] 定义为 背包为j容量 ，0-i 产品中任选一个，的效用。
# 初始化
def init_d():
    d = [ [ 0 for b in range(32001) ] for a in range(61)]    
    return d

def bag_0_1(d,values,utility,N,m):   
    for i in range(1,m+1):          #  物件
        for j in range(1,N+1):      #  背包                    
            d[i][j] = d[i-1][j]     #  没有满足任何件,取不到 i ; 
            if j >= values[i][0]:   #  仅仅满足主件
                d[i][j] = max(d[i][j],d[i-1][j-values[i][0]] + utility[i][0] )
            if j >= values[i][0]+values[i][1]:  # 满足主件 + 第 1 个附件 这里不取的时候，是 d[i][j]，d[i][j] 指的是 上一个if 的结果，像冒泡一样层层递进。
                d[i][j] = max(d[i][j],d[i-1][j-values[i][0]-values[i][1]] + utility[i][0]+utility[i][1])
            if j >= values[i][0]+values[i][2]:   # 满足主件 + 第 2 个附件
                d[i][j] = max(d[i][j],d[i-1][j-values[i][0]-values[i][2]] + utility[i][0]+utility[i][2])
            if j >= values[i][0]+values[i][1]+values[i][2]:  # 满足主件 + 第 1 和 第 2 个附件
                d[i][j] = max(d[i][j],d[i-1][j-values[i][0]-values[i][1]-values[i][2]] + utility[i][0]+utility[i][1]+utility[i][2] )
            # print('ok this is ',d[i][j])
            # result = d[i][j]
            # 从 5 种情况中找出最大 的 utility 效用。每种情况下 又分 取到这样的i 和没取到这样的 i 两种情况，取他们的最大值，注意 取不到的情况 就是退回到 上一个 if 语句下的 d[i][j] 了，因为他们是环环相扣的，目的就是找出 5种情况下的最大值。
    return d[i][j]

if __name__=='__main__':
    d = init_d()
    values,utility,N,m = build_structure()
    result = bag_0_1(d,values,utility,N,m)*10
    print(result)