C++背包实现

Question

我的背包算法有问题。老实说，我不知道哪里出了问题。当我使用一次程序时，一切都出错了，但是当我要循环使用我的程序（用于测试）时，我遇到了很多问题。

例如：
Weight/Val 在文件中：100
最大背包容量：1000
第一次迭代：
最大利润：2597
得到的权重：994/1000
很好，但现在是另一个迭代。
第二次迭代：
最大利润：2538
最终重量：1004/1000 <- 这是我的问题，它超过了我的最大上限。
第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

好的，所以当我只准备一次相同的 N（如上面示例中的 100）时，它工作正常，但是当我循环执行时：

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

C++背包实现

C++ knapsack implementation

c++

knapsack-problem