Implement the following java algorithm and modify it to count the number of node
ID: 3827335 • Letter: I
Question
Implement the following java algorithm and modify it to count the number of nodes visited and include the set of items in the solution.
public class Algorithmsixone {
void knapsack2 (int n, const int p[], const int w[], int W, int& maxprofit){
queue_of_node Q;
node u, v;
initialize (Q);
v.level = 0; v.profit = 0; v.weight = 0;
maxprofit = 0;
enqueue(Q, v);
while (!empty(Q)){
dequeue(Q, v);
u.level = v.level +1;
u.weight = v.weight + w[u.level];
u.profit = v.profit + p[u.level];
if(u.weight <= W && u.profit > maxprofit)
maxprofit = u.profit;
if(bound(u) > maxprofit)
enqueue(Q, u);
u.weight = v.weight;
u.profit = v.profit;
if(bound(u) > maxprofit)
enqueue(Q, u);
}
}
float bound (node u){
index j, k;
int totweight;
float result;
if(u.weight >= W)
return 0;
else{
result = u.profit;
j = u.level + 1;
totweight = u.weight;
while(j <= n && totweight + w[j] <= W){
totweight = totweight + w[j];
result = result + p[j];
j++;
}
k = j;
if(k <= n)
result = result + (W - totweight) * p[k]/w[k];
return result;
}
}
}
Explanation / Answer
Please take the reference from below working code :
public class Algorithmsixone
{
public void knapsack2(int[] wt, int[] val, int W, int N)
{
int NEGATIVE_INFINITY = Integer.MIN_VALUE;
int[][] m = new int[N + 1][W + 1];
int[][] sol = new int[N + 1][W + 1];
int count = 0;
for (int i = 1; i <= N; i++)
{
for (int j = 0; j <= W; j++)
{
int m1 = m[i - 1][j];
int m2 = NEGATIVE_INFINITY;
if (j >= wt[i])
m2 = m[i - 1][j - wt[i]] + val[i];
/** select max of m1, m2 **/
m[i][j] = Math.max(m1, m2);
sol[i][j] = m2 > m1 ? 1 : 0;
}
}
/** make list of what all items to finally select **/
int[] selected = new int[N + 1];
for (int n = N, w = W; n > 0; n--)
{
if (sol[n][w] != 0)
{
selected[n] = 1;
w = w - wt[n];
}
else
selected[n] = 0;
}
/** Print finally selected items **/
System.out.println(" Items selected : ");
for (int i = 1; i < N + 1; i++)
if (selected[i] == 1){
count++;
System.out.print(i +" ");
}
System.out.println();
System.out.println(" Number of nodes visited: " +count);
}