你的位置:首页 > 信息动态 > 新闻中心
信息动态
联系我们

UVa 1149背包问题

2021/11/4 2:40:50

ij分别是一个序列的最大最小值
难点在于理解取最大最小配对并不会增加背包
因为每个相对最大值总有比最小值更大的数配对,而这更大的数总有比最大值更小的数配对。

import random

#data
N = 1e5
M = random.randint(1,100)
all_w = [random.randint(1,100) for i in range(int(N))]
# code
all_w.sort(reverse=True)

 
bag = 0
i = 0
j = len(all_w)-1
while(i<=j):

    bag += 1
    if i==j:
        break
    if  all_w[i] + all_w[j]<=M:
        if j>0:j-=1
    if i<len(all_w)-1:
        i += 1
print(bag)