Czy istnieje taki algorytm?

Cześć,
załóżmy taki problem, że mamy wartość np 67 oraz skończony zbiór dodatnich liczb typu 21, 7, 8, 32, 11 itd i chciałbym znaleźć taki podzbiór liczb, który po zsumowaniu da nam wartość najbardziej przybliżoną do naszego wstępnego 67. Czy istnieje już algorytm, który rozwiązuje ów problem, lub podobny? Pytam się, bo nie ma sensu wymyślać koła a przydałoby mi się to.

Z góry dzięki

Hej,
looknij tutaj: http://www.coderscity.pl/viewtopic.php?t=50170

Brzmi jak wariacja nt. wydawania reszty. Może spróbuj zacząć od tego.

Brzmi jak SubsetSum albo bardziej problem plecakowy dyskretny -> https://pl.wikipedia.org/wiki/Problem_plecakowy

Tak, to problem plecakowy, dość znany, jest sporo podejść, od brute'a do bardziej skomplikowanych metod optymalizacji. Znaną metodą jest programowanie dynamiczne, wymaga ono skonstruowanie tablicy o wymiarach W x n, gdzie W to zawartość plecaka, a n ilość przedmiotów do upakowania. Wydaje mi się, że znalazłem prostą konstrukcję pozwalającą na uniknięcie powtarzania się wyników. Kod ma postać:

def knaps(W, a):
    V={a[0]:[a[0]]}
    for elem in a[1:]:
        elements = list(V.keys())[:]
        for key in elements:
            s = elem + key
            if s == W:
                return (W, V[key]+[elem])
            elif s < W:
                V[s] = V[key]+[elem]
    m = max(V.keys())
    return (m, V[m])

print(knaps(W, a)) 

W Twoim wypadku:

W = 67, a = [21, 7, 8, 32, 11]

Może komuś kod się przyda. Pozdrawiam :)

Wersja ulepszona, sprawdza elementy (i usuwa), które nic nie zmieniają w obliczeniach (dzięki Twojej @Shalom w sumie sugestii):

W = 11
a = 100000*[2] + [13]

def knaps(W, a):
    b = a[0]
    V={b:[b]}
    a = a[1:]
    while a:
        elem = a[0]
        elements = list(V.keys())[:]
        U = V.copy()
        for key in elements:
            s = elem + key
            if s == W:
                return (W, V[key]+[elem])
            elif s < W:
                V[s] = V[key]+[elem]
        a.remove(elem)
        if V==U:
            while elem in a:
                a.remove(elem)
    m = max(V.keys())
    return (m, V[m])

print(knaps(W, a))

i takie wypociny (świeże) problemu plecakowego z wagami, współrzędne: (weight, value).

W = 10
a = [[2, 6], [2, 4], [2, 3], [2, 1], [3, 7], [3, 7], [3, 4], [3, 1], [5, 6]]

def knaps_w(W, a):
    sorted(a, key=lambda x: (x[0], -x[1]))
    optima = 0
    opt_sol = []
    b = a[0]
    V = {b[0]:[[b[0]], b[1]]}
    a = a[1:]
    while a:
         elem = a[0]
         sss = list(V.keys())[:]
         for key in sss:
             s = elem[0] + key
             if s <= W:
                 if not s in V.keys():
                     V[s] = [V[key][0]+[elem[0]], elem[1]+V[key][1]]
                     if V[s][1] > optima:
                         optima = V[s][1]
                         opt_sol = V[s][0]
                 else:
                     if V[s][1] < elem[1]+V[key][1]:
                         V[s] = [V[key][0]+[elem[0]], elem[1]+V[key][1]]
                         if V[s][1] > optima:
                             optima = V[s][1]
                             opt_sol = V[s][0]
         a.remove(elem)
    return (optima, opt_sol)

print(knaps_w(W, a))

Podobne do poprzedniego, ale problem z wagami jest bardziej złożony, także nie będzie to szybko działać dla większej ilości elementów. Przydała się pomoc dwóch osób z równoległego wątku, trochę lepciejsze wyniki po odpowiednim posortowaniu danych. :)