手続き型ナップザック問題ブルートフォッサーをオブジェクト指向のものにするにはどうしたらいいですか？

Question

これはNP完成品knapsack problemをブルートフォースする私の最初のショットです。このフォームには、飛行機から投げ出されなければならないアイテムのリストがそれぞれ重量とコストで表示されます。目標は、コストを最小限に抑えながら、いくつかのremain_weightをスローすることです。

アイテムが選択された後、各再帰レベル（グラフの場合はy方向）が新しいremain_weightになります。 forループはすべてのアイテムを検索します（グラフの場合はx方向）

これらの2つの関数をクラスに入れるにはどのような方法が最適ですか？

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[]で機能することがわかります（いいえ、2D配列ではありません）。これらもメンバーになる可能性があります。

branchは混乱しているため少し複雑です。再帰的ですが、すべての再帰でitem_matrixも初期化します。 item_matrixをクラスに移動しても問題ありません。 ctorはそれを初期化します。しかし、同じ再帰的理由のために、そのクラスをbranch()の外に割り当ててください。

最後に、もう少しコンパクトにしてください。オブジェクトを早期に定義しないでください。値があるときにそれらを定義します。敢えて書くcout << "Entering at depth: " << ++depth_level;