C++ 구현 배낭 분기 및 바인딩

Question

분기 및 경계를 사용하여이 배낭 문제의 C++ 구현을 시도하고 있습니다. 여기에 본 웹 사이트의 자바 버전이 있습니다 : Implementing branch and bound for knapsack

내가 대신 내 C++ 버전은, 그러나 그것은 그 일을 아니에요해야한다는 (90)를 인쇄하기 위해 노력하고, 그것은 5.

합니까을 인쇄하는 것 누구는 그 문제가 어디에 있고 무엇이있을 수 있는지 알고 있습니까?

#include <queue> 
#include <iostream> 
using namespace std; 

struct node 
{ 
    int level; 
    int profit; 
    int weight; 
    int bound; 
}; 

int bound(node u, int n, int W, vector<int> pVa, vector<int> wVa) 
{ 
    int j = 0, k = 0; 
    int totweight = 0; 
    int result = 0; 

    if (u.weight >= W) 
    { 
     return 0; 
    } 
    else 
    { 
     result = u.profit; 
     j = u.level + 1; 
     totweight = u.weight; 

     while ((j < n) && (totweight + wVa[j] <= W)) 
     { 
      totweight = totweight + wVa[j]; 
      result = result + pVa[j]; 
      j++; 
     } 

     k = j; 

     if (k < n) 
     { 
      result = result + (W - totweight) * pVa[k]/wVa[k]; 
     } 
     return result; 
    } 
} 

int knapsack(int n, int p[], int w[], int W) 
{ 
    queue<node> Q; 
    node u, v; 
    vector<int> pV; 
    vector<int> wV; 
    Q.empty(); 

    for (int i = 0; i < n; i++) 
    { 
     pV.push_back(p[i]); 
     wV.push_back(w[i]); 
    } 

    v.level = -1; 
    v.profit = 0; 
    v.weight = 0; 

    int maxProfit = 0; 

    //v.bound = bound(v, n, W, pV, wV); 
    Q.push(v); 

    while (!Q.empty()) 
    { 
     v = Q.front(); 
     Q.pop(); 

     if (v.level == -1) 
     { 
      u.level = 0; 
     } 
     else if (v.level != (n - 1)) 
     { 
      u.level = v.level + 1; 
     } 

     u.weight = v.weight + w[u.level]; 
     u.profit = v.profit + p[u.level]; 

     u.bound = bound(u, n, W, pV, wV); 

     if (u.weight <= W && u.profit > maxProfit) 
     { 
      maxProfit = u.profit; 
     } 

     if (u.bound > maxProfit) 
     { 
      Q.push(u); 
     } 

     u.weight = v.weight; 
     u.profit = v.profit; 

     u.bound = bound(u, n, W, pV, wV); 

     if (u.bound > maxProfit) 
     { 
      Q.push(u); 
     } 
    } 
    return maxProfit; 
} 

int main() 
{ 
    int maxProfit; 
    int n = 4; 
    int W = 16; 
    int p[4] = {2, 5, 10, 5}; 
    int w[4] = {40, 30, 50, 10}; 

    cout << knapsack(n, p, w, W) << endl; 

    system("PAUSE"); 
} 

Answer 1

나는 당신이 잘못된 벡터에 이익과 무게 값을 넣었다고 생각합니다. 변경 :

int p[4] = {2, 5, 10, 5}; 
int w[4] = {40, 30, 50, 10}; 

에 :

int w[4] = {2, 5, 10, 5}; 
int p[4] = {40, 30, 50, 10}; 

및 프로그램을 출력 (90)

Answer 2

당신은 16 승을 설정하는, 그래서 결과는 당신이 고려할 수있는 유일한 항목 5입니다 배낭은 이익이 5이고 무게가 10 인 항목 3입니다.

Answer 3

나는 구현 한 것이 정확히 & 바운드 알고리즘이 아니라고 생각합니다. 나가 그것을 무언가와 일치해야하는 경우에 기초를 두는 추정에 훨씬이다.

알고리즘의 문제는 사용중인 데이터 구조입니다. 당신이하고있는 일은 먼저 모든 첫 번째 레벨을 밀어 넣은 다음 두 번째 레벨을 모두 밀어 넣은 다음 모든 세 번째 레벨을 대기열로 밀어 넣고 삽입 순서대로 다시 가져 오는 것입니다. 결과를 얻지 만 전체 검색 공간을 검색하는 것입니다.

요소를 삽입 순서로 팝하는 대신 가장 높은 예상 경계를 가진 노드에서 항상 분기하는 것이 필요합니다. 즉, 예상 범위와 관계없이 항상 모든 노드에서 분기됩니다. 브랜치 & 바운드 기법은 매번 단 하나의 노드에서 브랜칭을 통해 속도가 향상되므로 결과로 이어질 가능성이 가장 큽니다 (예상 값이 가장 높음).

예 : 첫 번째 반복에서 당신이 추정 값

노드 1로 2 개 노드를 발견했다고 가정 : (110)

노드 2 : 80

당신은 당신의 대기열로 모두를 추진하고있다 .

노드 3 : 95

하고 있습니다 : 100

노드 4 귀하의 큐는 노드 1 분기 후 2 개 이상의 노드를 밀고 두 번째 반복에서 "N2-N1-머리"가되었다 ("n4-n3-n2-head"라고도 함) 오류가 발생합니다. 다음 반복에서 얻는 것은 node2이지만 대신 가장 높은 예상 값을 갖는 node3이어야합니다.

그래서 대구에 뭔가를 놓치지 않으면 e 구현과 java 구현 모두 잘못되었습니다.우선 순위 큐 (힙)를 사용하여 실제 분기 &을 구현해야합니다.

Answer 4

 #include <bits/stdc++.h> 
using namespace std; 

struct Item 
{ 
    float weight; 
    int value; 
}; 
struct Node 
{ 
    int level, profit, bound; 
    float weight; 
}; 

bool cmp(Item a, Item b) 
{ 
    double r1 = (double)a.value/a.weight; 
    double r2 = (double)b.value/b.weight; 
    return r1 > r2; 
} 
int bound(Node u, int n, int W, Item arr[]) 
{ 
    if (u.weight >= W) 
     return 0; 
    int profit_bound = u.profit; 
    int j = u.level + 1; 
    int totweight = u.weight; 

    while ((j < n) && (totweight + arr[j].weight <= W)) 
    { 
     totweight = totweight + arr[j].weight; 
     profit_bound = profit_bound + arr[j].value; 
     j++; 
    } 
    if (j < n) 
     profit_bound = profit_bound + (W - totweight) * arr[j].value/
             arr[j].weight; 

    return profit_bound; 
} 

int knapsack(int W, Item arr[], int n) 
{ 
    sort(arr, arr + n, cmp); 
    queue<Node> Q; 
    Node u, v; 
    u.level = -1; 
    u.profit = u.weight = 0; 
    Q.push(u); 
    int maxProfit = 0; 
    while (!Q.empty()) 
    { 
     u = Q.front(); 
     Q.pop(); 
     if (u.level == -1) 
      v.level = 0; 

     if (u.level == n-1) 
      continue; 
     v.level = u.level + 1; 
     v.weight = u.weight + arr[v.level].weight; 
     v.profit = u.profit + arr[v.level].value; 
     if (v.weight <= W && v.profit > maxProfit) 
      maxProfit = v.profit; 
     v.bound = bound(v, n, W, arr); 
     if (v.bound > maxProfit) 
      Q.push(v); 
     v.weight = u.weight; 
     v.profit = u.profit; 
     v.bound = bound(v, n, W, arr); 
     if (v.bound > maxProfit) 
      Q.push(v); 
    } 

    return maxProfit; 
} 
int main() 
{ 
    int W = 55; // Weight of knapsack 
    Item arr[] = {{10, 60}, {20, 100}, {30, 120}}; 
    int n = sizeof(arr)/sizeof(arr[0]); 

    cout << "Maximum possible profit = " 
     << knapsack(W, arr, n); 

    return 0; 
} 
**SEE IF THIS HELPS**