Methods to solve fractional knapsack

0
votes

I have to implement two algorithms to solve fractional knapsack, but till now I have just found and implemented greedy method.

I have searched a lot for any other algorithm (as dynamic programming which I've read that it also can solve fractional knapsack, but I could not find any pseudo-code for it). All what I've found is about 0/1 knapsack.

Does anyone has links or any algorithm that can solve fractional knapsack?

3
algorithmknapsack-problem
Why do you want to use dynamic programming? A greedy algorithm from wikipedia article always gives a correct solution. – kraskevich
@user2040251 I think he needs to implement two algorithms just for comparison, probably for academic project etc. – Adam Stelmaszczyk
@Adam Stelmaszczyk what you said is true – yemany yemany

3 Answers

1
votes

@yola21 answer in java code:
Define the undefined functions by yourself, they are about accepting input from user.

//define your variables here 


        System.out.println("Enter number of items:");
        size = acceptNumberOfItems()

        System.out.println("Enter size of your knapsack:");
        size = acceptKnapsackSize()

        System.out.println("Enter weight of each item:");

        acceptWeightArray(weight)

        System.out.println("Enter value of each item:");

        acceptWeightArray(value)

        double[][] valuePerWeight = new double[size][2];

        double maxValue = 0;

        for(int i=0; i<size; ++i){
            valuePerWeight[i][0] = value[i]/weight[i];
            valuePerWeight[i][1] = weight[i];
        }

        java.util.Arrays.sort(valuePerWeight, new java.util.Comparator<double[]>() {
                    public int compare(double[] a, double[] b) {
                        return Double.compare(a[0], b[0]);
                    }
                });



        int i = size-1;
        while(knapsackSize > 0  && size >0){
            //while not full

            if(valuePerWeight[i][1] > knapsackSize){
                maxValue += knapsackSize * valuePerWeight[i][0];
                knapsackSize = 0;
            }
            else{

                maxValue +=  valuePerWeight[i][1] * valuePerWeight[i][0];
                knapsackSize -= valuePerWeight[i][1];
            }


            --i;
        }
        System.out.println("Max Value:" + maxValue);
    }
0
votes

You can use genetic algorithm.

If there are n materials, your chromosome will have n - 1 doubles from 0 to 1. i-th double designates how much material i we take. For material n, we take remainder, i.e. 1 - (sum of n - 1 doubles).

For example for n = 4 materials chromosome could be [0.1, 0.2, 0.3]. We take 0.1 of first meterial, 0.2 of the second one, 0.3 of third one and 0.4 of fourth one.

From what I understand it doesn't have to be very efficient, that it's just for comparison of different algorithms. So, you can start with random chromosomes, mutate them, discard weakest (smallest overall value), mutate them, discard weakest, and so on. You can also think about adding a crossover.

0
votes

I dont know what you mean by two algorithms but here is a solution for fractional knapsack problem.

very easy in comparison to 0/1 knapsack problem btw.

  1. prepare a third array, value per weight array, dividing weight of each item by its corresponding value

  2. sort the items in descending order according to their value per weight

  3. take item from item list into your sack till it is full

N.B Be sure to take the fraction of the last item if your sack could not fully accept it.

e.g if you have 80 k.g in you sack and the next item's weight is 23:
1. you have to take the 20 k.g
2. calculate the value of the 20 k.g out of the 23 k.g and add it to the total value you will get.