KnapSack1

import java.util.*;

public class Knapsack {

    public static double greedyKnapSack(ItemValue[] items, int capacity) {
        Arrays.sort(items, (a, b) -> Double.compare((double) b.profit / b.weight, (double) a.profit / a.weight));

        double totalProfit = 0;
        for (ItemValue item : items) {
            if (capacity >= item.weight) {
                capacity -= item.weight;
                totalProfit += item.profit;
            } else {
                totalProfit += (double) capacity / item.weight * item.profit;
                break;
            }
        }
        return totalProfit;
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        System.out.print("Enter number of items: ");
        int n = sc.nextInt();
        ItemValue[] items = new ItemValue[n];
        
        System.out.println("Enter weight and profit of each item:");
        for (int i = 0; i < n; i++) {
            items[i] = new ItemValue(sc.nextInt(), sc.nextInt());
        }

        System.out.print("Enter capacity: ");
        int capacity = sc.nextInt();
        
        System.out.println("Maximum profit: " + greedyKnapSack(items, capacity));
        sc.close();
    }
}

class ItemValue {
    int weight, profit;
    ItemValue(int weight, int profit) {
        this.weight = weight;
        this.profit = profit;
    }
}




function greedyKnapSack(items, n, W):
    sort items in descending order of (profit/weight)

    totalProfit = 0
    remainingCapacity = W

    for each item in items:
        if remainingCapacity >= item's weight:
            totalProfit += item's profit
            remainingCapacity -= item's weight
        else:
            fraction = remainingCapacity / item's weight
            totalProfit += fraction * item's profit
            break

    return totalProfit





Procedure GREEDY_KNAPSACK (P, W, M, X, n):

 and  contain the profits and weights respectively of the  objects arranged so that .

 is the knapsack size, and  is the solution vector.


real P(1:n), W(1:n), X(1:n), M, cu;  
integer i, n;  

X ← 0  // Initialize solution to zero  
cu ← M  // cu = remaining knapsack capacity  

for i ← 1 to n do  
    if W(i) > cu then exit endif  
    X(i) ← 1  
    cu ← cu - W(i)  
repeat  

if i ≤ n then X(i) ← cu/W(i) endif  

end GREEDY_KNAPSACK



OUTPUT:

Enter the number of items: 
3
Enter weight, profit of each item: 
10 60
20 100
30 120
Enter capacity: 
50
Maximum profit: 240.0