C++ 배낭 구현

Question

배낭 알고리즘에 문제가 있습니다. 솔직히 말해서 무엇이 잘못 됐는지 나는 모른다. 프로그램을 한 번 사용하면 모든 것이 잘못 작동하지만 프로그램을 루프 (테스트 용)로 사용할 때 많은 문제가 발생합니다.

예를 들어

: 파일
무게/발 : 100
최대 배낭 용량 : 1000
첫 번째 반복 :
최대 이익 : 2,597
결과 무게 : 1,000분의 994
그리고 그것의 좋은 ,하지만 이제는 또 다른 반복입니다.
두 번째 반복 :
최대 이익 : 2,538
결과 무게 : 1,000분의 1,004 < - 내 문제가 그 내 최대 캡 이상.
3 번째, 4 번째는 오키, 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]; 
     } 
    } 
} 

누군가가 내 문제 도와 드릴 :

내 기능은 가능한 문제인가?

Answer 1

좋아, 그래서 내가 (위의 예에서 100 등)은 같은 N 일단 준비 할 때 그것은 잘 작동하지만 내가 루프를 수행 할 때, 예를 들어 혼자 너무

   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), 다음 동일한 프로그램 쓰기 (51) 등등에 좋은 작동하지만, 내가 쓰기 (50), 다음 다른 쓰기 (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; 
      } 
     } 
    } 
}