I am having a lot of trouble with this knapsack problem. I have the branch and bound code working pretty smoothly, other than not being able to count the number of times it prunes correctly(2nd thing I need help with) and then I cannot get the dynamic programming code to work at all it keeps giving either a compiler error or a segmentation fault (1st thing I need help with). I will list the code as follows, can we try changing it as little as possible to get my two issues fixed? Thank you

// C++ program to solve knapsack problem using

// branch and bound

#include

using namespace std;

int Pruned = 0;

// Stucture for Item which store weight and corresponding

// value of Item

struct Item

{

float weight;

int value;

};

// Node structure to store information of decision

// tree

struct Node

{

// level --> Level of node in decision tree (or index

// in arr[]

// profit --> Profit of nodes on path from root to this

// node (including this node)

// bound ---> Upper bound of maximum profit in subtree

// of this node/

int level, profit, bound;

float weight;

};

// Comparison function to sort Item according to

// val/weight ratio

bool cmp(Item a, Item b)

{

double r1 = (double)a.value / a.weight;

double r2 = (double)b.value / b.weight;

return r1 > r2;

}

// Returns bound of profit in subtree rooted with u.

// This function mainly uses Greedy solution to find

// an upper bound on maximum profit.

int bound(Node u, int n, int W, Item arr[])

{

// if weight overcomes the knapsack capacity, return

// 0 as expected bound

if (u.weight >= W)

{

return 0;

}

// initialize bound on profit by current profit

int profit_bound = u.profit;

// start including items from index 1 more to current

// item index

int j = u.level + 1;

int totweight = u.weight;

// checking index condition and knapsack capacity

// condition

while ((j < n) && (totweight + arr[j].weight <= W))

{

totweight += arr[j].weight;

profit_bound += arr[j].value;

j++;

}

// If k is not n, include last item partially for

// upper bound on profit

if (j < n)

profit_bound += (W - totweight) * arr[j].value /

arr[j].weight;

return profit_bound;

}

// A Dynamic Programming based solution for 0-1 Knapsack problem

#include

// A utility function that returns maximum of two integers

int max(float a, float b) { return (a > b)? a : b; }

// Returns the maximum value that can be put in a knapsack of capacity W

int DPknapsack(int W, Item arr[0], int n)

{

int i , w = 0;

int K[n+1][W+1];

int val[n];

float wt[n];

// Build table K[][] in bottom up manner

for (i = 0; i <= n; i++)

{

val[i] = arr[i].value;

wt[i] = arr[i].weight;

}

for ( i = 0; i <= n; i++)

{

for (int w = 0; w <= W; w++)

{

if (i==0 || w==0)

K[i][w] = 0;

else if (wt[i-1] <= w)

K[i][w] = max(float(val[i-1] + K[i-1][w-wt[i-1]]), float( K[i-1][w]));

else

K[i][w] = K[i-1][w];

}

}

return K[n][W];

}

// Returns maximum profit we can get with capacity W

int BBknapsack(int W, Item arr[], int n)

{

// sorting Item on basis of value per unit

// weight.

sort(arr, arr + n, cmp);

// make a queue for traversing the node

queue Q;

Node u, v;

// dummy node at starting

u.level = -1;

u.profit = u.weight = 0;

Q.push(u);

// One by one extract an item from decision tree

// compute profit of all children of extracted item

// and keep saving maxProfit

int maxProfit = 0;

while (!Q.empty())

{

// Dequeue a node

u = Q.front();

Q.pop();

// If it is starting node, assign level 0

if (u.level == -1)

v.level = 0;

// If there is nothing on next level

if (u.level == n-1)

continue;

// Else if not last node, then increment level,

// and compute profit of children nodes.

v.level = u.level + 1;

// Taking current level's item add current

// level's weight and value to node u's

// weight and value

v.weight = u.weight + arr[v.level].weight;

v.profit = u.profit + arr[v.level].value;

// If cumulated weight is less than W and

// profit is greater than previous profit,

// update maxprofit

if (v.weight <= W && v.profit > maxProfit)

maxProfit = v.profit;

else

Pruned++;

// Get the upper bound on profit to decide

// whether to add v to Q or not.

v.bound = bound(v, n, W, arr);

// If bound value is greater than profit,

// then only push into queue for further

// consideration

if (v.bound > maxProfit)

Q.push(v);

// Do the same thing, but Without taking

// the item in knapsack

v.weight = u.weight;

v.profit = u.profit;

v.bound = bound(v, n, W, arr);

if (v.bound > maxProfit)

{

Q.push(v);

}

}

cout << "Branches Pruned in BB = " << Pruned+1<< endl;

return maxProfit;

}

// Random Number Generator function

void RandomNumbers (Item arr[], int n)

{

for (int i = 0; i< n; i++) // loop

{

arr[i].weight = (rand ()%n) + 1;

arr[i].value = (rand ()%n) + 1;

}

}

// driver program to test above function

int main()

{

srand(time(NULL));

int n = 1000;

Item arr[n];

int W = n*20;

RandomNumbers(arr, n);

cout << "DP Maximum possible profit = "

<< DPknapsack(W, arr, n) << endl;

cout << "-------------------------------" << endl;

cout << "BB Maximum possible profit = "

<< BBknapsack(W, arr, n) << endl;

cout << "-------------------------------" << endl;

return 0;

}