The breadth first search with branch-and-bound pruning code for the 0-1 knapsack problem
I typed code almost same way as pesudo code.
But it occurs error.
Exception in thread "main" java.lang.ArrayIndexOutOfBoundsException: 4
at knapsack_breadth.Ex1.knapsack2(Ex1.java:67)
at knapsack_breadth.Ex1.main(Ex1.java:136)
As i think,the cause is on the v.level
so when I call some value from an array with a index that is v.level
it bring me error about index out
after
u.level = v.level + 1;
value of v.level change to v.level + 1
ex) print(v.level); ---> 1
u.level = v.level + 1;
print(v.level); --->2
public class Ex1 {
public static int maxprofit;
public class node {
int level;
int profit;
int weight;
//Constructor of Node
}
public class Queue1 {
ArrayList<node> list = new ArrayList();
int size;
node deq;
void enqueue(node e){
list.add(e);
}
node dequeue(){
size = list.size();
if(size==0){
return null;
}
else{
deq = list.get(size-1);
list.remove(size-1);
return deq;
}
}
boolean isEmpty(){
size = list.size();
if(size==0){
return true;
}
else{return false;}
}
}
void knapsack2(int n,int p[],int w[],int weight){
Queue1 Q = new Queue1();
node u = new node();
node v = new node();
int count=0;
int store_v_level;
int store_v_weight;
int store_v_profit;
maxprofit = 0;
/*while(!is_empty(Q)){
Q.poll();
}*/ //Initialize Q to be empty
v.level=0; v.profit =0; v.weight=0; //Initialize v to be the root
Q.enqueue(v);
while (!Q.isEmpty()){ //while Q is not empty
v = Q.dequeue();
u.level = v.level + 1;
u.weight = v.weight + w[u.level-1];
u.profit = v.profit + p[u.level-1];
if(u.weight <= weight && u.profit > maxprofit){
maxprofit = u.profit;
}
if(bound(u,n,p,w,weight) > maxprofit){
Q.enqueue(u);
}
u.weight = v.weight;
u.profit = v.profit;
if (bound(u,n,p,w,weight) > maxprofit){
Q.enqueue(u);
count++;
}
}
System.out.println("maxprofit : " + maxprofit);
}
void node_test(){
Queue<node> Q = new LinkedList<node>();
node u = new node();
u.level = 1; u.weight = 1; u.profit = 1;
node v = new node();
v.level = 2; v.weight = 2; v.profit = 2;
}
float bound(node u,int n,int p[], int w[], int weight){
int j, k; // index
int totweight;
float result;
if(u.weight >= weight)
return 0;
else{
result = u.profit;
j = u.level + 1;
totweight = u.weight;
while ( j<=n && totweight + w[j-1] <= weight){
totweight += w[j-1];
result += p[j-1];
j++;
}
k=j;
if(k<=n){
result += (weight-totweight)*(p[k-1]/w[k-1]);
}
return result;
}
}
public static void main(String[] args){
Ex1 knapsack = new Ex1();
int p[] = {40,30,50,10};
int w[] = {2,5,10,5};
int weight = 16;
int n = 4;
System.out.println("start");
knapsack.knapsack2(n, p, w, weight);
}
}
