This program solves the fractional knapsack problem.

The problem :

There are

In Symbol, the fraction knapsack problem can be stated as follows.

maximize

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

The fractional knapsack problem solution is based on the

Code:

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

The problem :

There are

*n*items in a store. For i =1,2, . . . , n, item i has weight*w*> 0 and worth_{i }*v*> 0. Thief can carry a maximum weight of_{i }*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*x*of object_{i}*i*, where 0 ≤ x_{i}≤ 1. Item*i*contributes*x*to the total weight in the knapsack, and_{i}w_{i}*x*to the value of the load._{i}v_{i}In Symbol, the fraction knapsack problem can be stated as follows.

maximize

^{n}**S**_{i=1 }*x*subject to constraint_{i}v_{i}^{n}**S**_{i=1 }*x*_{i}w_{i}≤ WIt 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

^{n}**S**_{i=1 }*x*_{i}w_{i}= 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

## No comments:

## Post a Comment