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 wi > 0 and worth vi > 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:
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 wi > 0 and worth vi > 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
No comments:
Post a Comment