Sottrazione ottimizzata [RISOLTO]

[kearney]

Ciao a tutti! Vorrei girarvi un piccolo problema che mi appresto a risolvere. Sperando che qualcuno mi possa dare una dritta.
Dovrei realizzare un algoritmo che mi permetta di sottrarre da un valore costante una serie di valori variabili, riducendo al minimo lo scarto.
Faccio un esempio.
Ho una serie di botti da 1350lt di acqua che devo suddividere in altri contenitori più piccoli e di vario formato.
ad esempio:
n°2 da 450lt
n°4 da 295lt
n°5 da 114lt
n°3 da 75lt

se faccio le varie permutazioni con dei cicli ottengo:
(450+450+295+114)=1309 con una rimanenza di 41lt
in pratica faccio riempire prima i contenitori più grandi per poi proseguire con li altri, sempre che, ovviamente ci sia disponibilità di "liquido".

Però se lo si fa a mente, si vede che è più conveniente fare così:
(450+450+295+75+75)=1345 con una rimanenza di soli 5lt
Lo scopo in pratica è lasciare il minor numero di lt nella botte. Ovviamente l'ultima botte avrà un residuo maggiore di acqua ma poco male.

Magari è più semplice del previsto, ma essendo poco ferrato in matematica non so magari qualche nozioncina
Grazie a tutti coloro che mi daranno un'idea su come procedere.

[codino75]

"kearney":
se faccio le varie permutazioni con dei cicli ottengo:
(450+450+295+114)=1309 con una rimanenza di 41lt
in pratica faccio riempire prima i contenitori più grandi per poi proseguire con li altri, sempre che, ovviamente ci sia disponibilità di "liquido".

la strategia di riempire prima i contenitori piu' grandi sembra non portare al risultato ottimo del problema.
se non hai problemi di tempo basta che provi TUTTI i modi in cui puoi riempire i recipienti, cioe' trovando tutti i modi possibili di riempimento.
in questo modo trovi sicuramente l'ottimo, pero' devi vedere appunto se il tempo di computazione risulta adeguato o se e' troppo lungo.
ah, mi accorgo solo ora che non hai detto se il calcolo lo devi fare a mano o a mezzo calcolatore elettronico.
se a mano .......non saprei ..........ora c penso
ciao
alex

[kearney]

Dovrei realizzare un programmino propio per svolgere questo compito. Il problema mio è l'approccio. Provare tutte le possibili soluzioni credo sia la migliore, tuttavia non saprei come poterla implementare visto che dovrei tenere traccia delle combinazioni.
Forse dovrei pensare in maniera differente, cercando di arrivare alla soluzione attraverso un'altra strada..
Grazie Alex

Ciao

[codino75]

un modo molto semplice di tenere traccia delle varie 'scelte parziali' e' quello di considerare una stringa di bit di lunghezza 16, cioe':
000000000000000
in cui il bit i-esimo rappresenta se il recipiente i-esimo e' da riempire oppure no.
ovviamente suppongo che i recipienti siano stati numerati, ciascuno con un un numero (diverso) da 1 a 16.
poi devi fare in modo di incrementare la stringa di 1 unita' alla volta: c'e' un modo semplice per farlo ,
(ah ma non so se conosci la numerazione binaria)
per esempio per passare da
0011
a
0100
basta che per ogni bit fai l' 'and' tra i bit che lo seguono (verso destra), e cambia solo se tale 'and' restituisce 1 (tranne l'ultimo bit a destra che cambia sempre. (se non t e' chiaro posta)

ovviamente questa che ti propongo e' solamente UN possibile approccio (e nemmeno tanto elegante...
alex

[kearney]

"codino75":
ovviamente questa che ti propongo e' solamente UN possibile approccio (e nemmeno tanto elegante...

Ciao Alex, continuo a ringraziarti per la tua gentilezza e disponibilità.
Non è vero che non sia "elegante" perchè tutto sommato usando i bit riesci a ridurre i tempi e le risorse necessarie per la computazione.
Mi scoraggia dover creare una procedura che calcoli tutte le possibili combinazioni poichè essendo tanti i contenitori verrà esponenziale il risultato.
Ora non mi resta che capire come creare tutte le combinazioni esistenti... Magari spulcio il forum.. sperando di trovare qualcosa

(in fase pensante )

[codino75]

forse non mi sono spiegato abbastanza chiramente nel mio precedente post.
considera i seguenti numeri binari (letti per righe) (che possono essere implementati in codice tramite array):
000
001
010
011
100
101
110
111
ciascuno di essi e' il sucessivo del precedente
il nostro scopo e' generare uno dopo l'altro tutti i numeri binari indicati sopra e, per ciascuno calcolare l'avanzo di liquido corrispondente.
allora un frammento di pseuocodice (supponiamo di avere a disposizione le seguenti funzioni):

avanzo (array) /che prende l'array binario indicante le botti da riempire e restituisce il corrispondente avanzo di liquido
successivo (array) /che prende l'array binario indicante le botti da riempire e restituisce il suo 'successivo')

1 A=0000
STRINGA_OTTIMA=0000
2 AVANZO_ATTUALE=litri_totali
3 AVANZO_PRECEDENTE=litri_totali
4 AVANZO_OTTIMO=litri_totali
5 AVANZO_ATTUALE=avanzo(A)
7 if (AVANZO_ATTUALE 8 AVANZO_PRECEDENTE=AVANZO_ATTUALE
10 A=successivo(A)
11 vai a 5
11 fine

alla fine di questa procedura dovresti (salvo probabili miei errori) avere in STRINGA_OTTIMA la stringa che minimizza l'avanzo

se e' abbastanza chiaro nel prossimo post ti dico se vuoi come realizzare facilmente la funzione 'successivo (array) '
'ciao alex

[zorn1]

Non ho letto l'algoritmo ma è davvero un bel problema!

[kearney]

Rieccomi. Scusate il ritardo nel rispondervi, ma fine settimana sono stato fuori (non solo di testa )
Mi avevano consigliato anche "l'algoritmo dello zaino", che tuttavia mi dava il risultato analogo al mio.
Mi piace l'idea di Sergio, il quale ringrazio insieme a tutti voi che mi state aiutando , ora si tratta di "ritoccarlo".
Perchè i tipi di contenitori sono variabili. Quindi i cicli
-----------
for ($i = 0; $i <= 2; ++$i) {
for ($j = 0; $j <= 4; ++$j) {
for ($k = 0; $k <= 5; ++$k) {
for ($l = 0; $l <= 3; ++$l)
----------
non possono essere statici, ma devono essere dinamici. Perchè io ho fatto un esempio di 4 tipi di contenitori, ma possono arrivare fino a 20!
questo porzione di codice è "facilmente" modificabile
"sum = $i*450 + $j*295 + $k*114 + $l*75;"
in quanto basta fare un "for" su un array con tutti i tipi di contenitori.
Più difficile sono i cicli annidati del for: come poterli fare in maniera dinamica a seconda dei contenitori?


ciao

[codino75]

si puo' prevare con la ricorsione.. quello si' che e' un metodo elegante...

[kearney]

"codino75":si puo' prevare con la ricorsione.. quello si' che e' un metodo elegante...

Ho cominciato a modificare un pò il codice per adattarlo alle mie esigenze. Al momento faccio esaurire il "compitino" basandomi sui i cicli for così strutturati.
Avevo pensato anche io alla ricorsione... Sto cercando un modo propio per non essere soggetto ai cicli..
mumble mumble

vi tengo aggiornati

[TomSawyer1]

In realta', questo e' un caso particolare del problema dello zaino (guadagni=peso, qui), da te citato, che e' NP-completo, ma puo' essere risolto in tempo pseudo-polinomiale con la programmazione dinamica.

EDIT: Qui trovi il codice in C per risolverlo in tempo psuedo-polinomiale. Nota che hai bisogno solo di un vettore (cioe' v[]=w[]), nel tuo caso.

[kearney]

Mi sto dedicando a provare la soluzione da te proposta (ringrazia anche il tuo amico). Solo che ti chiedo qualche delucidazione visto che lo sto convertendo in delphi e non conosco il perl.

----------------------
\$num = @cap; -------> con questa istruzione assegni alla variabile num il numero di elementi del vettore "cap" giusto?


for (\$i = 1; \$i < @max; ++\$i) {
my \$f;
\$f = 1;
for (\$j = \$i; \$j < @max; ++\$j) {
\$f *= \$basi[\$j]; --------------> f = al prodotto di tutti i valori del vettore "basi". Non mi è ancora chiaro il motivo ma lo faccio fare anche io
}
push(@fact, \$f);
}

push(@fact, 1); ---------> Qui mi sfugge propio. A cosa assegni il valore 1:?:

\$r = \$r % \$fact[\$j]; ------> La percentuale per cosa sta?

----------------------

Grazie e scusa se approfitto di te

ciao

[TomSawyer1]

kearney, ti suggerisco di usare il codice che ti ho linkato. E' la soluzioni piu' veloce al tuo problema.

[kearney]

"TomSawyer":kearney, ti suggerisco di usare il codice che ti ho linkato. E' la soluzioni piu' veloce al tuo problema.

Ok propendo verso questa strada. Mi traduco in pascal il listato che mi hai linkato. Magari se posso vi chiedo delle delucidazioni su alcuni comandi C che non trovo corrispondenza con il Pascal.


Grazie

[kearney]

"Sergio":
Saggia decisione.
Voglio sperare sia chiaro che non intendo "tirarmi indietro", nel senso che se davvero ti andasse - per altri motivi - di capire qualcosa del Perl sono pronto a offrirti link e aiuto diretto.
E se potrò aiutarti nella conversione da C a Pascal (linguaggi che ho usato molto, ma non uso da anni) ne sarò lieto.
Buon lavoro!

Ma no figurati Sergio. Anzi ti devo ringraziare come devo ringraziare tutti voi che mi state aiutando. Mi farebbe piacere un aiuto nella conversione in pascal perchè ho delle difficoltà oggettive nel tradurre alcune istruzioni C.
Magari domani posto quello che ho fatto e chiedo numi sugli inghippi che ho trovato

Grazie ancora

[kearney]

Come promesso trascrivo il codice, ma ci sono dei piccoli dubbi

Listato originale - C

#define WEIGHT_BINS  100

double solve_knapsack(int nn, double *v, double *w, double W, int *choice)
{
  double *sol_table; //solution table
  double w_step = W / WEIGHT_BINS;
  
  //printf("W step is %g, %d items\n", w_step, nn);
  int rl = WEIGHT_BINS+1;  //row length
  sol_table = (double *)malloc(sizeof(double) * (nn+1) * rl);

  int *prev_choice = (int *)malloc(sizeof(int) * nn * rl);
  int *cur_choice = (int *)malloc(sizeof(int) * nn * rl);

  //take care of the first row for zero items
  for (int i=0; i < rl; i++)
    sol_table[i] = 0;
  memset(cur_choice, 0, sizeof(int)*nn*rl);

Listato corrispondente in Pascal (Delphi)

type
    PDouble = ^double;
    PInteger = ^integer;

const
  WEIGHT_BINS=100;
	
function solve_knapsack(nn:integer; v: PDouble; W:double; choice: PInteger):double;
var
  sol_table, prev_choice, cur_choice: PDouble;
  w_step : double;
  rl:integer;
  i:integer;
begin
  w_step:=W / WEIGHT_BINS;
  rl:= WEIGHT_BINS+1;

  New(sol_table);   -----> Meglio GetMem?


  for i:=0 to rl-1 do
    begin
      ...
    end;
  ...
end;

Che io sappia il corrispondente di Malloc in pascal è New(), che appunto alloca la memoria della variabile. Ma Malloc permette anche di allocare maggiore memoria come appunto indicato dall'istruzione C. Come la traduco?
Medesimo problema per il ciclo for. In C posso fare "sol_table = 0;", in pascal non è possibile visto che è stato dichiarato come puntatore double.
Infine il corrispettivo della funzione memset quale sarebbe?

Grazie a tutti

Fabio

[TomSawyer1]

Complimenti Sergio per la fatica e la precisione della traduzione, dato che il Pascal e' un linguaggio moolto meno potente del C. Motivo per cui consiglierei a kearney di scaricarsi qualche compilatore C gratuito .

[kearney]

"TomSawyer":Complimenti Sergio per la fatica e la precisione della traduzione, dato che il Pascal e' un linguaggio moolto meno potente del C. Motivo per cui consiglierei a kearney di scaricarsi qualche compilatore C gratuito .

Mi associo ai complimenti e ringrazio molto Sergio. Il problema del compilare è legato al fatto che, usando il Delphi, mi trovo più comodo per la realizzazione grafica del programmino.
Provo ad implementare il tutto

[kearney]

Pant pant....
A grandi linee dovrebbe essere così:

function solve_knapsack(nn: integer; var v: array of double; var w: array of double; wcap: double): double;
var
  sol_table: array of double;
  prev_choice, cur_choice, choice: array of integer;
  w_step, curw : double;
  rl:integer;
  i,j:integer;
  temp:integer;
begin
  w_step:=wcap / WEIGHT_BINS;
  rl:= WEIGHT_BINS+1;
  SetLength(sol_table, SizeOf(double)*(nn+1)*rl);
  SetLength(prev_choice, SizeOf(integer)*nn*rl);
  SetLength(cur_choice, SizeOf(integer)*nn*rl);

  for i:=0 to rl-1 do
    begin
      sol_table[i]:=0;
    end;
  FillChar(cur_choice, SizeOf(integer)*nn*rl, 0);

  for i:=1 to (nn+1) do
   begin
    sol_table[i*rl] := 0;
   end;

   for j:=1 to rl do
   begin
     curw:=w_step*j;
     if (w[i-1] <= curw) then
     begin
       temp:= floor((curw - w[i-1])/w_step);
       if ((v[i-1] + sol_table[(i-1)*rl + temp]) > sol_table[(i-1)*rl + j]) then
       begin
	  sol_table[i*rl + j]:= v[i-1] + sol_table[(i-1)*rl + temp];
	    // memcpy(&cur_choice[j*nn], &prev_choice[temp*nn], sizeof(int)*nn);
            // La copia vettore dovrebbe partire da cur_choice[j*nn]
            // ma il pascal non lo permette.
          cur_choice:=copy(prev_choice, temp*nn, SizeOf(integer)*nn);
	  cur_choice[j*nn + i-1]:=1;
       end;
     end
    else
     begin
        sol_table[i*rl + j]:=sol_table[(i-1)*rl + j];
	  // memcpy(&cur_choice[j*nn], &prev_choice[j*nn], sizeof(int)*nn);
          // La copia vettore dovrebbe partire da cur_choice[j*nn]
          // ma il pascal non lo permette.
        cur_choice:=copy(prev_choice,j*nn,(SizeOf(integer)*nn));
     end;
   // memcpy(prev_choice, cur_choice, sizeof(int)*nn*rl);
   prev_choice:=copy(cur_choice,0,SizeOf(integer)*nn*rl);
   end;
    // memcpy(choice, &cur_choice[(rl-1)*nn], sizeof(int)*nn);
    // Qui il compilatore da un errore in quanto il vettore choice,
    // dichiarato nelle variabili parametro della funzione
    // lo considera come Array e non Dynamic Array.
    // Spostato nelle variabili locali della funzione.
  choice:=copy(cur_choice,(rl-1)*nn,SizeOf(integer)*nn);
  solve_knapsack:= sol_table[(nn+1)*rl - 1];
end;

Dando per scontato di non aver fatto grandi errori, c'ho un problemino sulla funzione memcpy che io ho "tradotto" con Copy.
Come scritto nelle note, a differenza della funzione di C, non posso far partire la copia dal punto desiderato.
Scovate altre magagne?

[TomSawyer1]

Non hai bisogno anche del vettore w[], nel tuo caso, dato che i pesi sono uguali ai rispettivi valori.

[kearney]

"Sergio":Mi sa che ho perso i 5 centesimi
Credo dovresti sia dichiarare choice fuori della funzione, sia usarla in una chiamata della funzione solve_knapsack.

Più in generale, stai scrivendo la funzione ma non ancora il breve programma che la chiama.
Dovresti scrivere anche questo e magari decidere se eliminare il vettore w (come ti suggerisce TomSawyer) oppure, più banalmente, renderlo uguale a v all'inizio e poi eliminarlo in seguito.

Ho già provato a dichiarare choice come globale ma da il medesimo errore. Visto che non mi servirà "direttamente" come variabile procederò ad elimarla.
Per quanto riguarda W e V convivono unicamente perchè prima mi voglio accertare del corretto funzionamento della funzione per poi snellirla e renderla confacente alle mie richieste.
Sostituisco istruzioni come questa

memcpy(&cur_choice[j*nn], &prev_choice[j*nn], sizeof(int)*nn);

con

for i:=(j*nn) to (SizeOf(integer)*nn) do cur_choice[i]:=prev_choice[i];

Ora ultimo quesito... Come ringraziarvi? Siete stati tutti gentilissimi. Questo programma non sarà commerciale, quindi non aspettatevi un ringraziamento monetario ma è fatto per aiutare la mia ragazza in ufficio, quindi... non ci pensate nemmeno
Scherzi a parte, volevo veramente ringraziarvi di cuore. Non appena proseguo con il lavoro, se riesco a far funzionare questa "zainetto" vi posto il codice (casoma servisse per altri) e metto Risolto al topic