UVa 1149背包问题

wuchangjian2021-11-04 02:27:20编程学习

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)

相关文章

带你了解面试官超级喜欢问的JVM,offer拿到手软

带你了解面试官超级喜欢问的JVM,offer拿到手软

前言 随着阿巴阿巴在面试中愈战愈勇,这几天又约上面试了࿰...

java实现三只小猪称体重

森林里面住着三只小猪,最近又到了他们称体重的时候,请用程...

Spring AOP实践

面试说道AOP都会说作用是对每层记录日志。但从来都没真正实践过。 场景:...

发表评论    

◎欢迎参与讨论,请在这里发表您的看法、交流您的观点。