I need to write a branch and bound algorithm for the knapsack problem, I have lo
ID: 3603652 • Letter: I
Question
I need to write a branch and bound algorithm for the knapsack problem, I have looked at one provided by geeksforgeeks and I am basing mine around that, but I come to a problem when I try to count the number of branches being pruned. I do not know how to code it to properly count the pruned branches, the site's code is as follows:
// C++ program to solve knapsack problem using
// branch and bound
#include <bits/stdc++.h>
using namespace std;
// 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;
}
// Returns maximum profit we can get with capacity W
int knapsack(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<Node> 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;
// 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);
}
return maxProfit;
}
// driver program to test above function
int main()
{
int W = 10; // Weight of knapsack
Item arr[] = {{2, 40}, {3.14, 50}, {1.98, 100},
{5, 95}, {3, 30}};
int n = sizeof(arr) / sizeof(arr[0]);
cout << "Maximum possible profit = "
<< knapsack(W, arr, n);
return 0;
}
For this specific example, I should get about 7 branches were pruned, I believe. Everything I have tried results in Pruned = 0. I would appreciate any help, even if the code must be changed immensely
// C++ program to solve knapsack problem using
// branch and bound
#include <bits/stdc++.h>
using namespace std;
// 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;
}
// Returns maximum profit we can get with capacity W
int knapsack(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<Node> 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;
// 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);
}
return maxProfit;
}
// driver program to test above function
int main()
{
int W = 10; // Weight of knapsack
Item arr[] = {{2, 40}, {3.14, 50}, {1.98, 100},
{5, 95}, {3, 30}};
int n = sizeof(arr) / sizeof(arr[0]);
cout << "Maximum possible profit = "
<< knapsack(W, arr, n);
return 0;
}
For this specific example, I should get about 7 branches were pruned, I believe. Everything I have tried results in Pruned = 0. I would appreciate any help, even if the code must be changed immensely
Explanation / Answer
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <vector>
#include <string>
#include <iostream>
using namespace std;
int knapsack(int value[], int weight[], int n, int C,
vector < int >&back)
{
int *M = new int[C + 1];
int k;
int i, j, tmp, pos;
for (i = 1; i <= C; i++) {
M[i] = M[i - 1];
pos = i - 1;
for (j = 0; j < n; j++) {
k = i - weight[j];
if (k >= 0)
tmp = M[k] + value[j];
if (tmp > M[i]) {
M[i] = tmp;
}
}
back.push_back(pos);
}
int ans = M[C];
delete[]M;
return ans;
}
int main()
{
int C, N;
cin >> C >> N;
int* value = new int[N+1];
int* weight = new int[N+1];
for ( int i = 0; i <= N; i++) {
cin>>value[i]>>weight[i];
}
vector < int >back(N, 0);
cout<<knapsack(value,weight,N,C,back)<<endl;
return 0;
}
int M[2000][2000];
int knapsack(int value[], int weight[], int C, int n)
{
for(int i = 1; i <= C; i++){
for(int j = 0; j <n; j++){
if(j > 0){
M[j][i] = M[j-1][i];
if (weight[j] <= i)
M[j][i] = max(M[j][i], M[j-1][i-weight[j]]+value[j]);
}
else{
M[j][i] = 0;
if(weight[j] <= i)
M[j][i] = max(M[j][i], value[j]);
}
}
// cout << M[i][n-1] << endl;
}
return M[n-1][C];
}
int main()
{
int C, N;
cin >> C >> N;
// cout << C << endl;
int* value = new int[N+1];
int* weight = new int[N+1];
for ( int i = 0; i < N; i++) {
cin>>weight[i]>>value[i];
}
// vector < int >back(N, 0);
cout<<knapsack(value,weight,C,N)<<endl;
return 0;
}
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
vector<int> v, c;
int B(int i, int w)
{
if (i == 0 || w == 0) return 0;
if (c[i] > w) return B(i - 1, w);
return max(B(i - 1, w), v[i] + B(i - 1, w - c[i]));
}
int main()
{
int S, N; cin >> S >> N;
// sloted in for easy array access; values won't be used.
c.push_back(-1);
v.push_back(-1);
int ct, vt;
for (int i = 0; i < N; i++) {
cin >> ct >> vt;
c.push_back(ct);
v.push_back(vt);
}
cout << B(N, S);
}
#include <vector>
#include <iostream>
#include <iomanip>
#include <string>
struct item {
int value;
int capacity;
};
class Knapsack {
public:
Knapsack(int knapsack_size, int item_size);
~Knapsack();
void add_items(int value, int capacity);
int solve();
void get_items_selected(std::vector<item>& resultItems);
friend std::ostream &operator <<( std::ostream&, const Knapsack& );
private:
void init_knapsack_table();
std::vector<item> m_items;
int m_knapsack_size;
int m_item_size;
// 2D matrix to store intermediate
// result of the knapsack calculation.
std::vector<std::vector<int> > m_knapsack_table;
// 2D matrix to store the intermediate
// result for which item is selected
// Later this matrix is used to get which items
// are selected for optimal calculation.
std::vector<std::vector<int> > m_selection_table;
protected:
};
Knapsack::Knapsack(int knapsack_size, int item_size):
m_knapsack_size(knapsack_size),
m_item_size(item_size),
m_knapsack_table(item_size + 1,std::vector<int>(knapsack_size + 1)),
m_selection_table(item_size + 1,std::vector<int>(knapsack_size + 1)){
m_items.reserve(m_item_size);
}
void Knapsack::add_items(int value, int capacity) {
item t;
t.value = value;
t.capacity = capacity;
m_items.push_back(t);
}
int Knapsack::solve() {
// Initialize the first row in both the
// tables, these values are used as default
// as if no items are selected and no capacity
// is available.
// This is the default case for bottom-up approach.
for ( int i = 0; i < m_knapsack_size + 1 ; i++) {
m_knapsack_table [0][i] = 0;
m_selection_table[0][i] = 0;
}
int row = 1;
for ( std::vector<item>::iterator itemIterator = m_items.begin();
itemIterator != m_items.end();
++itemIterator) {
item currentItem = *itemIterator;
int col = 0; // col is capacity available.
while ( col < m_knapsack_size + 1 ) {
//1. Check if item can be fit by it's own.
if ( currentItem.capacity > col ) {
//2. Get the solution for the already solved
// knapsack problem.
m_knapsack_table[row][col] = m_knapsack_table[row - 1][col];
// Update the selection table as we are not able to accomodate this item
// eventually we are not selecting this ite.
m_selection_table[row][col] = 0;
} else {
// We are now considering the item.
int capacity_remaining = col - currentItem.capacity;
int new_value = currentItem.value + m_knapsack_table[row - 1][capacity_remaining];
int prev_value = m_knapsack_table[row - 1][col];
if ( prev_value >= new_value) {
// There is no gain here to consider this item.
m_knapsack_table[row][col] = m_knapsack_table[row - 1][col];
m_selection_table[row][col] = 0;
} else {
// Add this item into the knapsack.
m_knapsack_table[row][col] = new_value;
// Update the selection table as we are considering
// this item.
m_selection_table[row][col] = 1;
}
}
col++;
}
row++;
}
return m_knapsack_table[m_item_size][m_knapsack_size];
}
void Knapsack::get_items_selected(std::vector<item>& resultItems) {
int row = m_item_size;
int col = m_knapsack_size;
int cap = m_knapsack_size;
while ( cap > 0 ) {
if ( m_selection_table[row][col] == 1) {
resultItems.push_back(m_items[row - 1]);
cap = cap - m_items[row - 1].capacity;
col = cap;
}
row = row - 1;
}
}
std::ostream &operator << (std::ostream &out, const Knapsack &knp ) {
out << std::endl;
out << "SOLUTION MATRIX" << std::endl << std::endl;
out << std::setw(15) << "Capacity |";
for ( int i = 0; i <= knp.m_knapsack_size; i++) {
out << std::setw(5) << i ;
}
out << std::endl;
out << std::endl;
int row = 0;
out << std::setw(15) << "NONE |";
int col = 0;
while ( col < knp.m_knapsack_size + 1 ) {
out << std::setw(5) << knp.m_knapsack_table[row][col];
col++;
}
out << std::endl;
row++;
for ( std::vector<item>::const_iterator itemIterator = (knp.m_items).begin();
itemIterator != knp.m_items.end();
++itemIterator) {
out << "(V:"
<< std::setw(2)
<< itemIterator->value
<< ", "
<< "W:"
<< itemIterator->capacity
<< ")"
<< std::setw(4)
<< "|" ;
col = 0;
while ( col < knp.m_knapsack_size + 1 ) {
out << std::setw(5) << knp.m_knapsack_table[row][col];
col++;
}
row++;
out << std::endl;
}
out << std::endl;
out << "SELECTION MATRIX" << std::endl << std::endl;
out << std::setw(15) << "Capacity |";
for ( int i = 0; i <= knp.m_knapsack_size; i++) {
out << std::setw(5) << i ;
}
out << std::endl;
out << std::endl;
row = 0;
out << std::setw(15) << "NONE |";
col = 0;
while ( col < knp.m_knapsack_size + 1 ) {
out << std::setw(5) << knp.m_knapsack_table[row][col];
col++;
}
out << std::endl;
row++;
for ( std::vector<item>::const_iterator itemIterator = (knp.m_items).begin();
itemIterator != knp.m_items.end();
++itemIterator) {
out << "(V:"
<< std::setw(2)
<< itemIterator->value
<< ", "
<< "W:"
<< itemIterator->capacity
<< ")"
<< std::setw(4)
<< "|" ;
col = 0;
while ( col < knp.m_knapsack_size + 1 ) {
out << std::setw(5) << knp.m_selection_table[row][col];
col++;
}
row++;
out << std::endl;
}
return out;
}
Knapsack::~Knapsack() {
}
int main ( int argc, char **argv) {
Knapsack knp(18,7);
knp.add_items(12,4 );
knp.add_items(10,6 );
knp.add_items(8 ,5 );
knp.add_items(11,7 );
knp.add_items(14,3 );
knp.add_items(7 ,1 );
knp.add_items(9 ,6 );
int solution = knp.solve();
std::cout << knp;
std::vector<item> resultItems;
knp.get_items_selected(resultItems);
std::cout << "SOLUTION" << std::endl;
std::cout << ' ' << "Value : " << solution << std::endl;
std::cout << ' ' << "Items : " << std::endl;
for ( std::vector<item>::iterator itr = resultItems.begin();
itr != resultItems.end();
++itr) {
std::cout << ' ' << ' ' << "(V:"
<< std::setw(2)
<< itr->value
<< ", "
<< "W:"
<< itr->capacity
<< ")"
<< std::endl;
}
return 0;
}