KnapSack (NEW)

import java.util.*;

public class Knapsack {
    public static double greedyKnapSack(ItemValue[] arr, int capacity) {
        // Sort items based on their profit-to-weight ratio in descending order
        Arrays.sort(arr, new Comparator<ItemValue>() {
            public int compare(ItemValue item1, ItemValue item2) {
                double cpr1 = (double) item1.profit / item1.weight;
                double cpr2 = (double) item2.profit / item2.weight;
                if (cpr1 < cpr2)
                    return 1;
                else
                    return -1;
            }
        });

        double total = 0;

        for (ItemValue i : arr) {
            if ((capacity - i.weight) >= 0) {
                // If the item can be fully taken
                capacity -= i.weight;
                total += i.profit;
            } else {
                // Take the fraction of the item
                double fract = (double) capacity / (double) i.weight;
                total += fract * (i.profit);
                capacity = 0;
                break;
            }
        }

        return total;
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        System.out.println("Enter the number of items: ");
        int n = sc.nextInt();
        ItemValue[] arr = new ItemValue[n];

        System.out.println("Enter weight, profit of each item: ");
        for (int i = 0; i < n; i++) {
            arr[i] = new ItemValue(sc.nextInt(), sc.nextInt());
        }

        System.out.println("Enter capacity: ");
        int m = sc.nextInt();

        double pro = greedyKnapSack(arr, m);
        System.out.println("Maximum profit: " + pro);
    }
}

class ItemValue {
    public int weight;
    public int profit;

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



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