我如何让我的过程性背包问题变成一个面向对象的问题？

Question

这是我第一次尝试暴力逼迫NP-complete knapsack problem。在这个表单中，您有一个必须从飞机上抛出的物品列表，每个物品都有重量和成本。目标是在最小化成本的同时丢弃一些remain_weight。

在选择项之后，每个递归级(如果绘制为y方向)都是一个新的remain_weight。一个for循环搜索所有的项目(如果有图形，x方向)

Test Case 1 - Works
Item / Weight / Cost
0      100     101
1      300     297

将这两个函数放在一个类中的最佳方法是什么？

enum item_type {weight, cost};
int algo(int &cost_low, int &cost_high, int throw_weight, int item_id, int item_matrix[][2])
{
    int quantity,remainder;
    quantity=throw_weight/item_matrix[item_id][weight];
    remainder=throw_weight%item_matrix[item_id][weight];
    if(remainder==0)
    {
        cost_low=(quantity-1)*item_matrix[item_id][cost];
        cost_high=quantity*item_matrix[item_id][cost];
        throw_weight-=(quantity-1)*item_matrix[item_id][weight];
    }
    else
    {
        cost_low=(quantity)*item_matrix[item_id][cost];
        cost_high=(quantity+1)*item_matrix[item_id][cost];
        throw_weight-=(quantity)*item_matrix[item_id][weight];
    }
    return throw_weight;
}
int branch(int remain_weight)
{
    static int depth_level = 0;
    static int cost_present=32000;
    int remain_weight_next;
    int cost_low, cost_high, cost_branch;
    depth_level++;
    cout << "Entering at depth: " << depth_level << " :remain_weight: " << remain_weight << endl ;
    int item_id, item_count=2; 
    int item_matrix[][2] = 
    {
        {100, 101},
        {300, 297},
    //  {400, 401},
    //  {800, 800}, 
    //  {1200, 1200}, 
    //  {1999, 1800},
    //  {2000, 2000},
    };
    for(item_id=0; item_id<item_count; ++item_id)
    {
        cout << "--For loop id is: " << item_id << endl; 
        if(item_matrix[item_id][weight]<remain_weight)
        {
            cout << "----item_weight: " << item_matrix[item_id][weight] << " : is less than remain_weight : " << remain_weight << endl;
            remain_weight_next=algo(cost_low,cost_high,remain_weight,item_id,item_matrix); 
            cost_branch = branch(remain_weight_next);
            cost_present=cost_low + cost_branch;  
            if(cost_present>cost_high)
                cost_present=cost_high;
            cout << "--**remain_weight: " << remain_weight << endl;
            cout << "--**cost_low: " << cost_low << endl;
            cout << "--**cost_high: " << cost_high << endl;
            cout << "--**cost_branch: " << cost_branch << endl;
        }
        else
        {
            cout << "----item_weight: " << item_matrix[item_id][weight] << " : is greater than remain_weight : " << remain_weight << endl;
            if(cost_present>item_matrix[item_id][cost])
                cost_present=item_matrix[item_id][cost];
        }
        cout << "--**cost_present: " << cost_present << endl;
    }
    cout << "Leaving at Depth: " << depth_level << endl;
    depth_level--;
    return cost_present;
}

Answer 1

int &cost_low, int &cost_high是一个告密者。如果一个函数被重复调用，并且在每次迭代中修改相同的对象，那么该函数和那些对象可能应该是同一个类的成员。

如果你进一步观察，你会发现algo也可以在cost_matrix[]和weight_matrix[]上工作(不，它不是二维数组)。这些人也可以成为会员。

branch有点复杂，因为你把事情搞混了。它是递归的，但你也会在每次递归中初始化item_matrix。一旦你把item_matrix移到一个类中，没有问题；然后ctor会初始化它。但是出于同样的递归原因，一定要在branch()之外分配那个类。

最后，更紧凑一点。不要过早地定义对象；当你有一个值的时候再定义它们。敢写cout << "Entering at depth: " << ++depth_level;