Knapsack problem(dinamičko programiranje)

Znam da dobar dio vas zna za ovaj problem,pa bih zamolio da mi netko napiše kod za njega,našao sam neko šugavo objašnjenje na engleskom,koje ne razumijem....

Zadatak ide tako da lopov ima ruksak kapaciteta K i kako mu je policija za petama,pokušava ga popuniti tako da vrijednost u ruksaku bude najveća.Svaki predmet odlikuje veličina( kn ) i vrijednost (vn),program treba ispisati najveću moguću vrijednost koju lopov u tom trenutku može ponijeti...Ulazni podaci su N(broj predmeta) , K (kapacitet ruksaka) i zatim u N redova vn(vrijednost) i kn(veličina) svakog predmeta.

Hvala unaprijed,ako je moguće neka u kodu nabaci koji komentar :)

To sam i ja prvotno radio,ali to je greedy algoritam i ne prolazi :/

Pa onda mi daj neki link normalni ,jer ga ja u nisam u stanju nać :/

Recimo da ti predmet s najvećim omjerom (npr 1.01) zauzima 90 % kapaciteta, a sljedeći predmeti na listi imaju omjer vrijednosti npr 1 i zauzimaju 20 % kapaciteta i nakon 5 takvih imaš predmet koji zauzima 10 % kapaciteta i ima omjer 0,5.

Po tvom algoritmu bi imao prvi predmet i zadnji predmet i vrijednost 0,959, dok bi odabirom ovih 5 predmeta manje vrijednosti imao ukupnu vrijednost 1.

  Znam kako ti je...

Tako sto mi kreativna (desna) strana mozga nadjacava onu logicku (lijevu). Programiranjem sam se prije 11 godina poceo samo iz jednog razloga, htio sam stvarati. Citanje o algoritmima (pogotovo algoritmima ovakve vrste) i nekakvo teoriziranje meni nije zanimljivo (opet utjecaj desne strane). S druge strane, kada neki problem treba vizualizirati u glavi, tu sam kao riba u vodi. Tako uglavnom i rijesavam programske probleme, ono sto ne mogu vizualizirati, ne mogu rijesiti.

http://www.angelfire.com/wi/2brains/

http://www.web-us.com/brain/braindominance.htm

http://www.wherecreativitygoestoschool.com/vancouver/left_right/rb_test.htm

A sigurno si negdje vidio i onaj test sa balerinom koja se okrece, koji pokazuje koja ti je strana mozga aktivnija u tom trenutku...

Puno se moze reci na tu temu, ali cu te ostaviti da sam istrazujes a i debeli je offtopic. Samo cu na kraju zakljuciti da sam ja ono sto se dobije kada se osoba sa dominantnom desnom stranom mozga pokusa baviti programiranjem :D

Kod mene je slična situacija. Meni je lakše kad nešto mogu nekako vizualizirati. Zato volim OOP.

Evo jedan uvod:

http://www.cs.berkeley.edu/~vazirani/algorithms/all.pdf

Milslim da vam ja mogu pomoci. Nisam suguran dokle ste stigli i sto ima u onim materijalima jer nisam citao vase prijasnje postove, pa je moguce da moj post bude viska.

Vidio sam da je netko predlagao "greedy"  odnosno pohlepno rjesenje, tako da uzme najvrijednije odnosno stvari s najboljim odnosom.

Takva rjesenja prolaze u slucajevima kada imamo krhke elemente tj. mozemo uzeti neki dio elementa, a padaju u određenim slucajevima kada imamo krute elemente tj moramo ga uzeti cijelog ili nikako. Recimo nekakva zlatna prasina i zlatne poluge bio bi dobar odnos.

Kao kod svakog dinamickog programiranja tako i tu cilj je da se zapamti svako poznato stanje, te da se stoga smo jednom racuna.

Iako se u implementaciji da sacuvati puno prostora ja cu ovdje objasniti na "najneoptimalniji" nacin.

Daklo stanje DP-a cemo prikazati kao uređeni par dp(x, y) -> najbolje rjesenje (najveca tezina) koja ce stati u ruksak velicine y, koristeci prvih x elemenata.

Dakle kada gradimo dp tablicu to ce izgledati nesto tipa ovo :

Za svaki element znamo njegovu velicinu(V[i]) te vrijednost(C[i]).

V C

2 2

3 3

4 5

U ovome slucaju se mozda poklope greedy i dp rjesenje ali nije mi se dalo smisljati jedno gdje greedy pada, no siguran sam da uz malo mozganja to mozete smisliti.

Uzimam da svakog elementa imamo beskonacno mnogo, a kasnije cemo obraditi i 0-1 verziju gdje svakog imam jedan.

Dakle : Neka nam redovi tablice govore koliko elemenata koristimo, a stupci koliko velik ruksak koristimo :

   1 2 3 4 5 6

1 0 2 2 4 4 6  

2 0 2 3 4 5 5

3 0 2 3 5 5 7

Dakle vidimo da je rjesenje koristeci gornja tri elementa 7, tj mozemo ostvariti vrijednost 3.

Sto se da iscitati iz prvog retka, koristeci samo 1. element u ruksak velicine 1 mozemo ostvariti vrijednost 0, jer element nije moguce staviti.

U ruksak velicine 2. moguce je staviti jedan element velicine 2 i ostvariti vrijednost 2, u ruksak velicine 4 moguce je staviti 2 elementa velicine 2 te ostvariti vrijednost 4 ....

Dakle prvi redak popunjavamo pomocu sljedece relacije. dp[1][i] = dp[1][i-V[i]] + C[i];  to znaci koliko sam stavio 1. elemenata u ruksak velicine i-V[i] + 1element sto sada stavljam.

dakle u ruksak velicine 3 stavimo jedan element i ostane nam 1 jedinica prostora prazna. // i-oznacava velicinu ruksaka.

U drugom retku imamo sljedecu logiku. U ruksak velicine 1 nije moguce staviti nista(niti prvi niti drugi element), u ruksak velicine 2 moguce je staviti samo prvi element, pa ga i uzimamo.

Eh sada u ruksak velicine 3 gledamo jeli bolje staviti 1 1. element ili 1 2. element ispada da je bolje staviti 1 2. element. ruk velicine 4, jeli bolje staviti 2 1.elementa ili 1 2. element ispada da je bolje staviti 2 1. itd.

Dakle sada popunjavamo relacijom dp[2][i] = max( dp[1][i], dp[2][i-V[i]] + C[i] );

... istom logikom dalje.

1-0 verzija. Svakog elementa ima samo jedan.

   1 2 3 4 5 6

1 0 2 2 2 2 2

2 0 2 3 3 5 5

3 0 2 3 5 5 7

Logka je u principu ista samo sto se uvijek gleda na prosli red. Ako nekih elemenata imate vise, gledajte ih razdvojeno.

Kada zelite ocitati dp tablicu onda jos morate imati array gdje spremate koji ste element stavili. Znaci if dp[j-V[i]]  + C[i] > dp[j] best[j] = i;

Evo kod :

#include <cstdio>
#include <algorithm>
#include <cstring>

using std::max;

const int MAXN = 100; // maksimalan broj stvari
const int MAXV = 100; // maksimalan volumen

int V[ MAXN ]; // velicina elementa
int C[ MAXN ]; // cijena elementa

int dp1[ MAXN ][ MAXN ]; // 1-0 verzija
// [stavi koristeno][velicina ruksaka]
int dp2[ MAXN ];

int N, W; // broj elemenata i volumen

int main()
{
  scanf( "%d%d", &N, &W );
  for ( int i = 0; i < N; ++i )
    scanf( "%d%d", V+i, C+i ) ;

  memset( dp1, 0, sizeof dp1 );
  memset( dp2, 0, sizeof dp2 );

  // 1-0
  for ( int i = 0; i < N; ++i ) // iteriram po elementima
    for ( int j = 0; j <= W; ++j ) { // iteriram po velicini ruksaka
      if ( i == 0 && V[i] <= j ) dp1[i][j] = C[i]; // ako stane u ruksak
      else if ( V[i] <= j )
    dp1[i][j] = max( dp1[i-1][j], dp1[i-1][j-V[i]] + C[i] );
      else
    dp1[i][j] = dp1[i-1][j];
      // sto je bolje napuniti ruksak samo sa i-1 stvari
      // ili je bolje napuniti j-V[i] stvari s i-1 stavit i
      // staviti i-tu stvar ovdje
    }

  for ( int i = 0; i < N; ++i, putchar('\n') )
    for ( int j = 0; j <= W; ++j )
      printf( "%3d", dp1[i][j] );

  printf( "%d\n", dp1[N-1][W] );

  // verzija gdje svake stvari imamo beskonacno
  for( int i = 0; i < N; ++i )
    for ( int j = 0; j <= W; ++j )
      if ( V[i] <= j )
    dp2[j] = max( dp2[j], dp2[j-V[i]] + C[i] );

  printf( "%d\n", dp2[W] );
}
Nadam se da sam bio od pomoci.

Ako postoje neke nejasnoce javite se.

EDIT : I naravno i pogotovo greske !!