BUSYMAN SPOJ Greedy C

Algorithm:

1. Sort on end times.
2. Iterate over sorted list
        2.1 If the current activity overlaps, skip it
        2.2 If it doesn't increase count of answer. Set new time to end time of this activity.

Code: 

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_i > 0 and worth v_i > 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 x_i of object i, where 0 ≤ x_i ≤ 1. Item i contributes x_iw_i to the total weight in the knapsack, and x_iv_i to the value of the load.
In Symbol, the fraction knapsack problem can be stated as follows.
maximize ⁿS_i=1 x_iv_i subject to constraint ⁿS_i=1 x_iw_i ≤ 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 ⁿS_i=1 x_iw_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