Knapsack

Συζητήσεις για προετοιμασία για τον διαγωνισμό, online διαγωνισμούς, βιβλία προγραμματισμού και αλγορίθμων, και όλων των σχετικών.
Απάντηση
pman
Δημοσιεύσεις: 419
Εγγραφή: Τρί Φεβ 10, 2009 9:49 pm

Knapsack

Δημοσίευση από pman »

Ψάχνω ψάχνω.... μα ποτέ δεν μπορώ να βρω ένα καλό πηγαίο κώδικα κάπου για να μελετήσω το knapsack καλά. Γνωρίζει κανείς το πρόβλημα? Εάν ναι εάν μπορεί ας το γράψει σε C/C++.
:( :( :(
userresu
Δημοσιεύσεις: 191
Εγγραφή: Τρί Δεκ 16, 2008 9:53 pm

Re: Knapsack

Δημοσίευση από 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
Δημοσιεύσεις: 712
Εγγραφή: Κυρ Δεκ 21, 2008 2:45 pm

Re: Knapsack

Δημοσίευση από thetrojan01 »

απλά διάβασε τα έγγραφα που σου έστειλα, αν τα είχες ανοίξει θα βλεπες ότι έχουν και ψευδοκώδικα.
svyr cercrv an inevrfnv cbyl tvn an gb iyrcrvf nhgb... cvtrar xnzvn ibygn yrj tj.
pman
Δημοσιεύσεις: 419
Εγγραφή: Τρί Φεβ 10, 2009 9:49 pm

Re: Knapsack

Δημοσίευση από pman »

thetrojan01 έγραψε:απλά διάβασε τα έγγραφα που σου έστειλα, αν τα είχες ανοίξει θα βλεπες ότι έχουν και ψευδοκώδικα.
Τα διάβασα αλλά στο τελευταίο βήμα δεν κατάλαβα τι ζητούσε.
pman
Δημοσιεύσεις: 419
Εγγραφή: Τρί Φεβ 10, 2009 9:49 pm

Re: Knapsack

Δημοσίευση από pman »

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


Ευχαριστώ.
Απάντηση