C++ナップザックの実装

Question

ナップザックアルゴリズムに問題があります。正直言って私は何が間違っているのか分からない。私がプログラムを一度使うと、すべてうまくいきますが、私のプログラムをループ（テスト用）で使用するときには、大きな問題があります。例えば

：100
最大ナップザック容量：：1000
最初の反復：
最大利益：2597
結果の重量：1000分の994
とその細かいファイルに
重量/ヴァルしかし、今度は別の反復です。
2回目の反復：
最大利益：2538
結果の重量：1000分の1004 < - と私の問題があり、その私の最大のキャップを超えます。
3番目、4番目はokey、5番目は間違っていた（1355/1000）などです。

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]; 
     } 
    } 
} 

誰かが私の問題を支援することができます：？可能な問題である

My機能

Answer 1

私は（上記の例では100のように）同じN度だけ準備ができたときにそう、それは正常に動作しますが、私はループの中でそれを行う際に、[OK]を：

   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 
       } 

ので、私は例えば自分でやります私は間違ったアルゴリズムを書いている（50）、次に別の書き込み（50）を行うとき、それは良い作品が、同じプログラムの書き込み（51）などで書き込み（50）
私がソートを行うと、別のループでナップザックがうまくいきませんが、他の手ではまずソートを行う必要があります。
私のソート機能

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; 
      } 
     } 
    } 
}