सी ++ नापसैक शाखा के कार्यान्वयन और बाध्य

Question

मैं शाखा और बाध्यकारी का उपयोग करके इस knapsack समस्या के सी ++ कार्यान्वयन की कोशिश कर रहा हूं। यहाँ इस वेबसाइट पर एक जावा संस्करण है: Implementing branch and bound for knapsack

मैं अपने सी ++ संस्करण बाहर 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. केवल आइटम आप में ले सकता है knapsack लाभ 5 और वजन 10 के साथ आइटम 3 है।

Answer 3

मुझे विश्वास है कि आप जो कार्यान्वित कर रहे हैं वह शाखा & बाध्य एल्गोरिदम बिल्कुल नहीं है। अगर मुझे किसी चीज़ से मेल खाना पड़े तो यह एक अनुमान आधारित बैकट्रैकिंग की तरह है।

आपके एल्गोरिदम में समस्या डेटा संरचना है जिसका आप उपयोग कर रहे हैं। आप जो कर रहे हैं वह पहले सभी स्तरों को पहले धक्का देना है, और फिर सभी दूसरे स्तरों को धक्का देना, और फिर कतार में सभी तीसरे स्तर को धक्का देना और उन्हें सम्मिलन के क्रम में वापस लेना है। आपको अपना परिणाम मिल जाएगा लेकिन यह केवल पूरी खोज स्थान खोज रहा है।

तत्वों को उनके सम्मिलन आदेश के साथ पॉप करने के बजाय आपको जो करना है वह हमेशा उस नोड पर शाखा बनाना है जिसका उच्चतम अनुमानित सीमा है। दूसरे शब्दों में आप हमेशा अपने अनुमानित सीमाओं के बावजूद अपने रास्ते में हर नोड पर शाखा बना रहे हैं। शाखा & बाध्य तकनीक प्रत्येक गति केवल एक एकल नोड पर ब्रांचिंग से प्राप्त करती है जो परिणाम की ओर ले जाने के लिए सबसे अधिक संभावना है (उच्चतम अनुमानित मूल्य है)।

उदाहरण: आपकी पहली यात्रा में मान लें कि आप अनुमान मूल्यों

node1 के साथ 2 नोड्स पाया है: 110

node2: 80

आप उन दोनों को अपने कतार में बढ़ा रहे हैं । आपकी कतार "n2-n1 सिर" बन गया दूसरा यात्रा आप node1 पर शाखाओं के बाद दो और नोड्स बढ़ा रहे हैं में:

node3: 100

node4: 95

और आप कर रहे हैं उन्हें कतार में भी जोड़ना ("n4-n3-n2-head"। त्रुटि आती है। अगले पुनरावृत्ति में जो आप प्राप्त करने जा रहे हैं वह नोड 2 होगा लेकिन इसके बजाय यह नोड 3 होना चाहिए जिसका उच्चतम अनुमानित मूल्य है।

तो अगर मुझे आपके कोड में कुछ याद नहीं है ई आपके कार्यान्वयन और जावा कार्यान्वयन दोनों गलत हैं।वास्तविक शाखा & बाध्य करने के लिए आपको प्राथमिकता कतार (ढेर) का उपयोग करना चाहिए।

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**