Knapsack

[pman]

Ψάχνω ψάχνω.... μα ποτέ δεν μπορώ να βρω ένα καλό πηγαίο κώδικα κάπου για να μελετήσω το knapsack καλά. Γνωρίζει κανείς το πρόβλημα? Εάν ναι εάν μπορεί ας το γράψει σε C/C++.

[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 η αξία του.

[thetrojan01]

απλά διάβασε τα έγγραφα που σου έστειλα, αν τα είχες ανοίξει θα βλεπες ότι έχουν και ψευδοκώδικα.

[pman]

απλά διάβασε τα έγγραφα που σου έστειλα, αν τα είχες ανοίξει θα βλεπες ότι έχουν και ψευδοκώδικα.

Τα διάβασα αλλά στο τελευταίο βήμα δεν κατάλαβα τι ζητούσε.

[pman]

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

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 η αξία του.

Ευχαριστώ.