Knapsack

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

Knapsack

Δημοσίευση από sotiris » Τρί Ιουν 15, 2010 11:41 pm

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

userresu
Δημοσιεύσεις: 191
Εγγραφή: Τρί Δεκ 16, 2008 9:53 pm

Re: Knapsack

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

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

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 » Τετ Ιουν 16, 2010 9:48 am

απλά διάβασε τα έγγραφα που σου έστειλα, αν τα είχες ανοίξει θα βλεπες ότι έχουν και ψευδοκώδικα.
svyr cercrv an inevrfnv cbyl tvn an gb iyrcrvf nhgb... cvtrar xnzvn ibygn yrj tj.

sotiris
Δημοσιεύσεις: 422
Εγγραφή: Τρί Φεβ 10, 2009 9:49 pm

Re: Knapsack

Δημοσίευση από sotiris » Τετ Ιουν 16, 2010 10:18 am

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

sotiris
Δημοσιεύσεις: 422
Εγγραφή: Τρί Φεβ 10, 2009 9:49 pm

Re: Knapsack

Δημοσίευση από sotiris » Τετ Ιουν 16, 2010 10:19 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 η αξία του.


Ευχαριστώ.
Εικόνα

Απάντηση