пара цены товара в рамках бюджета - PullRequest
Новая
       5

пара цены товара в рамках бюджета

1 голос
/ 14 апреля 2020

Я пытался попрактиковаться в бинарном поиске. Цель состоит в том, чтобы найти пару цен в рамках бюджета. 

def binary_search(arr, lo, hi, x):
    while lo < hi: 
        count = 0
        sum = arr[lo] + arr[hi]
        if sum <= x:
            result = [arr[lo], arr[hi]]
            print(result)
            count += 1
            return binary_search(arr, lo, hi-1, x)
        else:
            return binary_search(arr, lo, hi-1, x)

A = [1, 2, 3, 4, 6, 7, 8]
print(binary_search(A, 0, len(A)-1, 10))

Как видите, я могу найти только первый товар с остальными: 

(1,8)
(1,7)
(1,6)
(1,5)
(1,4)
(1,3)
(1,2)

конечно, Я могу сделать это снова, используя 

return binary_search(arr, lo+1, hi, x)

в функции, чтобы найти другие пары, но это не идеально.

или я могу использовать itertools очень простым способом. 

from itertools import combinations
A = [1, 2, 3, 4, 6, 7, 8]
budget = 10
comb = combinations(A, 2)
answer = []

for i in list(comb):
    if sum(i) <= 10:
        print(I)
        answer.append(i)
print(len(answer))
print(answer)

Есть ли лучшие способы справиться с этим с помощью бинарного поиска. Любая помощь высоко ценится!

...