Witam. Mam do napisania program rozwiazujacy problem plecakowy dla dwoch plecakow. Dane wygladaja tak:
pojemnosc_pierwszego plecaka pojemnosc_drugiego_plecaka
liczba przedmiotow
wartosc_przedmiotu waga
wartosc_przedmiotu waga
....
Bez problemu napisalem program w c++, ktory dziala w czasie 2n . I w tym jest problem, poniewaz dla testow z 1000 przedmiotow ma sie on wykonywac ponizej 3 sekund ( na maszynie serwerowej, na pc bedzie to kilkanascie sekund tak mysle ), a moje 21000 nie jest raczej optymalnym czasem dla takich testow. W moim algorytmie sprawdzalem po prostu wszystkie mozliwosci. Wynik nie moze byc przyblizony, poniewaz maszyna testowa chce poprawnego wyniku. Prosze o pomoc kogos, kto juz spotkal sie z takim problemem.