## Sunday, September 14, 2014

### Fractional Knapsack Problem Solution [Fractional Knapsack][Java]

This program solves the fractional knapsack problem.

The problem :

There are n items in a store. For i =1,2, . . . , n, item i has weight w> 0 and worth v> 0. Thief can carry a maximum weight of W pounds in a knapsack. In this version of a problem the items can be broken into smaller piece, so the thief may decide to carry only a fraction xi of object i, where 0 ≤ xi ≤ 1. Item i contributes xiwi to the total weight in the knapsack, and xivi to the value of the load.
In Symbol, the fraction knapsack problem can be stated as follows.
maximize nSi=1 xivi subject to constraint nSi=1
xiwi ≤ W
It is clear that an optimal solution must fill the knapsack exactly, for otherwise we could add a fraction of one of the remaining objects and increase the value of the load. Thus in an optimal solution nSi=1 xiwi = W.

The fractional knapsack problem solution is based on the greedy approach where the best-looking step is taken at each choice. (In this case, the highest ratio item is selected from all the items).

Code:

```import java.util.Scanner;

public class FractionalKnapsack {

double weight[];
double benefit[];
double ratio[];
double W;

FractionalKnapsack() {
Scanner scan = new Scanner(System.in);
System.out.println("Enter the number of items in the store: ");
int nItems = scan.nextInt();
System.out.println("Enter the (weight and benefit) of items: ");
weight = new double[nItems];
benefit = new double[nItems];
ratio = new double[nItems];

for (int i = 0; i < nItems; ++i) {
weight[i] = scan.nextDouble();
benefit[i] = scan.nextDouble();
ratio[i] = benefit[i] / weight[i];
}

System.out.println("Enter the weight of the knapsack: ");
W = scan.nextDouble();
}

int getNext() {
double highest = 0;
int index = -1;
for (int i = 0; i < benefit.length; ++i) {
if (ratio[i] > highest) {
highest = ratio[i];
index = i;
}
}
return index;
}

void fill() {
double cW = 0; //current weight
double cB = 0; //current benefit

System.out.print("\nItems considered: ");
while (cW < W) {
int item = getNext();        //next highest ratio
if (item == -1) {
//No items left
break;
}

System.out.print((item+1)+" ");
if (cW + weight[item] <= W) {
cW += weight[item];
cB += benefit[item];
//mark as used for the getNext() (ratio) function
ratio[item] = 0;
} else {
cB += (ratio[item] * (W - cW));
cW += (W - cW);
break;  //the knapsack is full
}
}
System.out.println("\nMax Benefit = " + cB + ", Max Weight = " + cW);
}

public static void main(String[] args) {
FractionalKnapsack fk = new FractionalKnapsack();
fk.fill();
}
}```

Output:

Enter the number of items in the store:
5
Enter the (weight and benefit) of items:
20 4
40 3
10 1
35 5
40 2
Enter the weight of the knapsack:
50

Items considered: 1 4
Max Benefit = 8.285714285714285, Max Weight = 50.0