Algorytm najtańszego wyboru

Mam problem z wymyśleniem odpowiedniego algorytmu.
Mianowicie chodzi głownie o technikę zachłanną i o programowanie dynamiczne.

Podaną mam listę (paczek z jedzeniem dla lepszego zobrazowania) w której zawierają się 3 elementy:
x y z
x- oznacza liczbę marchewek
y- oznacza liczbę gruszek
z- oznacza koszt takiej paczki

Przykładowa lista może wyglądać tak:

8 5 15 
4 2 9 
4 3 5
7 8 20
itd

Następnie podaną mam liczbę marchewek i gruszek jakie mam zdobyć. Np 12 marchewek oraz 8 gruszek.
Działanie algorytmy ma polegać na tym że wypisze mi które paczki muszę kupić by wyszło jak najtaniej oraz by ilość potrzebnych rzeczy się zgadzała (nie moze być mniejsza ani większa). Paczka może być wybrana tylko raz.

Na początku chciałem liczyć ile kosztuje jeden przedmiot w danej paczce i tak wkładać do tablicy sortując ją od najtańszych do najdroższych. Dodając do siebie wiersze sprawdzając czy ilość nie została przekroczona. Jedna taki algorytm raczej nie przejdzie ponieważ najtańsza paczka na początku nie zawsze jest dobrym wyborem. Może ktoś ma jakiś inny pomysł ?

Problem jest podobny do http://pl.wikipedia.org/wiki/Problem_wydawania_reszty tylko zamiast minimalizować ilość monet, minimalizujesz sumę cen.

@Wibowit to nie ten problem.

A czy ja napisałem, że to ten problem? Napisałem, że jest podobny. Mogę dodać, że bardziej niż problem plecakowy, bo w problemie plecakowym nie ma warunku, że suma musi być równa tylko musi być nie większa niż jakiś tam limit.

Masz strasznie brzydki kod dla interpretera Pythona 2.7:

import itertools

class Paczka:
	def __init__(self,x=0,y=0,z=0):
		self.marchewki=x
		self.gruszki=y
		self.koszt=z
	def __repr__(self):
		return "(marchewki: %d, gruszki: %d, koszt: %d)"%(self.marchewki,self.gruszki,self.koszt)
	
	def __add__(self,other):
		return Paczka(self.marchewki+other.marchewki,self.gruszki+other.gruszki,self.koszt+other.koszt)

def dopasuj_paczki_do_celu(paczki,cel):
	wszystkie_kombinacje=[]
	for i in range(1,len(paczki)+1):
		wszystkie_kombinacje+=list(itertools.combinations(paczki,i))
	
	pasujace_kombinacje=[]
	for dana_kombinacja in wszystkie_kombinacje:
		a=Paczka()
		for i in dana_kombinacja:
			a=a+i
		if a.marchewki==cel.marchewki and a.gruszki==cel.gruszki:
			pasujace_kombinacje.append(dana_kombinacja)
	return pasujace_kombinacje

def sumy_kosztow(kombinacje):
	sumy=[]
	for i in kombinacje:
		k=0
		for j in i:
			k+=j.koszt
		sumy.append(k)
	return sumy
	
def najtanszy_zestaw(pasujace_kombinacje):
	sumy=sumy_kosztow(pasujace_kombinacje)
	return min(zip(pasujace_kombinacje,sumy),key=lambda x:x[1])[0]
		

cel=Paczka(12,8)

mozliwe_paczki=[Paczka(8,5,15),Paczka(4,2,9),Paczka(4,3,5),Paczka(7,8,20)]

print najtanszy_zestaw(dopasuj_paczki_do_celu(mozliwe_paczki,cel))

Powinien działać dla Twojego przykładu ;) Nie jest odporny na błędy. Np. jeśli nie ma paczek dokładnie spełniających cel, to przy return z funkcji najtanszy_zestaw może się wykrzaczyć.

Co do działania to:

1. Mega nieoptymalnie buduję tablicę wszystkich kombinacji koszyków bez powtórzeń.
2. Wyodrębniam kombinacje spełniające cel (dokładna ilość marchewek i gruszek).
3. Z wyodrębnionych kombinacji wyznaczam taką, która ma najniższą cenę.

Wzor rekurencyjny do DP bedzie wygladal tak:
C(i, j) = min{C(i-D[k].marchewki, j-D[k].gruszki) + D[k].cena}
gdzie C(i, j) jest kosztem za zestaw paczek z i marchewekami, j gruszkami.

Przy czym za kazdym razem gdy znajdujesz minium dla (i,j) zapamietujesz przedmiot, ktory wybrales, zeby nie wybrac go ponownie.