Σελίδα 1 από 1

Knapsack

Δημοσιεύτηκε: Τρί Ιουν 15, 2010 11:41 pm
από sotiris
Ψάχνω ψάχνω.... μα ποτέ δεν μπορώ να βρω ένα καλό πηγαίο κώδικα κάπου για να μελετήσω το knapsack καλά. Γνωρίζει κανείς το πρόβλημα? Εάν ναι εάν μπορεί ας το γράψει σε C/C++.
:( :( :(

Re: Knapsack

Δημοσιεύτηκε: Τετ Ιουν 16, 2010 12:34 am
από userresu

Κώδικας: Επιλογή όλων

for (int i=1;i<=MAXCAP;++i)
best[i]=0;
for (int i=1;i<=MAXCAP;++i)
for (int j=1;j<=MAXITEM;++j)
if (i>=a[j] && best[i]<best[i-a[j]]+value[j])
best[i]=best[i-a[j]]+value[j];
Όπου best το μεγαλύτερο κέρδος που μπορείς να έχεις με capacity=i, a ο όγκος του αντικειμένου i και value η αξία του.

Re: Knapsack

Δημοσιεύτηκε: Τετ Ιουν 16, 2010 9:48 am
από thetrojan01
απλά διάβασε τα έγγραφα που σου έστειλα, αν τα είχες ανοίξει θα βλεπες ότι έχουν και ψευδοκώδικα.

Re: Knapsack

Δημοσιεύτηκε: Τετ Ιουν 16, 2010 10:18 am
από sotiris
thetrojan01 έγραψε:απλά διάβασε τα έγγραφα που σου έστειλα, αν τα είχες ανοίξει θα βλεπες ότι έχουν και ψευδοκώδικα.
Τα διάβασα αλλά στο τελευταίο βήμα δεν κατάλαβα τι ζητούσε.

Re: Knapsack

Δημοσιεύτηκε: Τετ Ιουν 16, 2010 10:19 am
από sotiris
userresu έγραψε:

Κώδικας: Επιλογή όλων

for (int i=1;i<=MAXCAP;++i)
best[i]=0;
for (int i=1;i<=MAXCAP;++i)
for (int j=1;j<=MAXITEM;++j)
if (i>=a[j] && best[i]<best[i-a[j]]+value[j])
best[i]=best[i-a[j]]+value[j];
Όπου best το μεγαλύτερο κέρδος που μπορείς να έχεις με capacity=i, a ο όγκος του αντικειμένου i και value η αξία του.


Ευχαριστώ.