Question

How to recursive solve a fractional Knapsack problem in Java with log(n) time.

Note!! And return a boolean array of each being take(T) or not take(F)

0-1 Knapsack Problem Weight 10; Value 60; Weight 20; Value 100; Weight = 30; Value = 120; Weight = (20+10): Value = (100+60); Weight = (30+10): Value = (120+60); Weight = (30+20): Value = (120+100); Weight = (30+20+10) > 50 value1 = {60, 100, 120); weigh 3(10, 20, 30); W = 50; Solution: 220

this output shoud be: take=[0,1,1]

static double[] fractionalKnap(double[] values, int[] weights, int k) {

double[] take = new double[values.length]; ​

return take;

}

Answer 1

Solution:

code:

import java.util.Random;

class Knapsack {

   public static int TotalValueknapSack(int Bag, int weight[], int value[], int N) {

       if (N == 0 || Bag == 0)
           return 0;

       if (weight[N - 1] > Bag)
           return TotalValueknapSack(Bag, weight, value, N - 1);

       else
           return Math.max(value[N - 1] + TotalValueknapSack(Bag - weight[N - 1], weight, value, N - 1),
                  
                   TotalValueknapSack(Bag, weight, value, N - 1));
   }

   public static void main(String args[]) {
       Random r = new Random();
       int value[] = new int[5];
       int weight[] = new int[5];
       for (int i = 0; i < 5; ++i) {
           value[i] = r.nextInt(100)+1; // values is between 50 to 200
           weight[i] = r.nextInt(19) + 1; // wight is between 1 to 20
       }
      
       for (int i = 0; i < 5; ++i)
           System.out.print(value[i] + " ");
           System.out.println();
       for (int i = 0; i < 5; ++i)
           System.out.print(weight[i] + " ");
       System.out.println();
      
       int bag = 20;// Bag is of weight 20
       System.out.println("The total Value of knapsack is " + TotalValueknapSack(bag, weight, value, weight.length));
   }
}

I hope this helps if you find any problem. Please comment below. Don't forget to give a thumbs up if you liked it. :)