import java.util.*; public class Knapsack { public static double greedyKnapSack(ItemValue[] arr, int capacity) { 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) { capacity -= i.weight; total += i.profit; } else { 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(pro); } } class ItemValue { public int weight; public int profit; public ItemValue(int weight, int profit) { this.weight = weight; this.profit = profit; } }
Preview:
downloadDownload PNG
downloadDownload JPEG
downloadDownload SVG
Tip: You can change the style, width & colours of the snippet with the inspect tool before clicking Download!
Click to optimize width for Twitter