C++ Rucksack Implementierung

Question

Ich habe ein Problem mit meinem Rucksack-Algorithmus. Um ehrlich zu sein, ich habe keine Ahnung, was falsch ist. Wenn ich Programm einmal benutze, funktioniert alles falsch, aber wenn ich mein Programm in Schleife (für Test) verwende, habe ich ein großes Problem.

Zum Beispiel:
Gewicht/Val in der Datei: 100
max Kapazität Ranzen: 1000
Erste Iteration:
Max Gewinn: 2597
Das resultierende Gewicht: 994/1000
Und seine feinen , aber jetzt eine weitere Iteration.
Zweite Iteration:
Max Gewinn: 2538
Das resultierende Gewicht: 1004/1000 < - und es ist mein Problem, sein über meine max Kappe.
3., 4. war okey, dann 5. war falsch (1355/1000), und so weiter.

Meine Funktion ist, wo möglich Problem:

void intoKnapsack(int k, float actual_profit, float actual_weight) 
{ 
    if (actual_weight + weight[k] <= cap) 
    { 
     tmp[k] = 1; 
     if (k <= number_items) 
      intoKnapsack(k + 1, actual_profit + value[k], actual_weight + weight[k]); 
     if (((actual_profit + value[k]) > final_profit) && (k == number_items)) 
     { 
      final_profit = actual_profit + value[k]; 
      final_weight = actual_weight + weight[k]; 
      for (j = 0; j <= k; j++) 
       knap[j] = tmp[j]; 
     } 
    } 
    else if ((bound(actual_profit, actual_weight, k) >= final_profit)) 
    { 
     tmp[k] = 0; 
     if (k <= number_items) 
      intoKnapsack(k + 1, actual_profit, actual_weight); 
     if ((actual_profit > final_profit) && (k == number_items)) 
     { 
      final_profit = actual_profit; 
      final_weight = actual_weight; 
      for (j = 0; j <= k; j++) 
       knap[j] = tmp[j]; 
     } 
    } 
} 

Kann jemand bei meinem Problem helfen?

Answer 1

Ok, also wenn ich nur einmal die gleiche N (wie 100 in obigem Beispiel) dann bereit es funktioniert gut, aber wenn ich es in Schleife tun:

   srand((unsigned int) time(NULL)); 
       algorytm a; 
       fstream wynik; 
       wynik.open("result.txt",ios::out | ios::app); 
       for(int i=0; i<how_test; i++){ //how many tests 
        write(how_n); //how many n in my file, and create file 
        a.read()  //read from file (n, and weight/val) 
        time_start(); 
        a.sort();  //I sort it 
        a.intoKnapsack(0, 0.0, 0.0); //my function above, so I give here a 3x to do it properly over and over in loop 
        get_time(); //stop time 
        measurement+=get_time(); 
        result<<get_time()<<" s."<<endl; //just for 
       } 

so, wenn ich zum Beispiel von mir tun schreibe (50), dann im selben Programm schreibe (51) und so weiter, es funktioniert gut, aber wenn ich schreibe (50), dann schreibe ich einen anderen (50), dann habe ich einen falschen Algorithmus.
Vielleicht wenn ich sortiere, bevor klar Knapsack es in einer anderen Schleife funktioniert nicht, aber in der anderen Hand muss ich zuerst sortieren.
Es ist meine Sortierfunktion

void algorytm::sort() { 

    int a; 
    int b; 
    float c; 
    for (i = 0; i < number_items; i++) 
     factor[i] = (float) val[i]/(float) weight[i]; //to sort from best to worst 
    for (i = 0; i < number_items - 1; i++) { 
     for (j = i + 1; j < number_items; j++) { 
      if (factor[i] < factor[j]) { 
       c = factor[i];       // 
       factor[i] = factor[j]; 
       factor[j] = c; 
       a = val[i];         // 
       val[i] = val[j]; 
       val[j] = a; 
       b = weight[i];         // 
       weight[i] = weight[j]; 
       weight[j] = b; 
      } 
     } 
    } 
}