@Test public void testSolveByBestRatioFirst(){ KnapsackInstanceWithSolution p = KnapsackInstanceWithSolution.problemP05(); boolean[] heavier = GreedyForKnapsack.solveByHeavierFirst(p.getProblem()); boolean[] ratio = GreedyForKnapsack.solveByBestRatioFirst(p.getProblem()); assertArrayEquals(heavier, ratio); }
public static boolean[] solveByBestRatioFirst(KnapsackProblem problem){ List<KnapsackProblem.Item> items = problem.getCopyOfItems(); items.sort((a,b) -> { if(a.getWeight() == 0){ return -1; } if(b.getWeight() == 0){ return 1; } double ra = a.getValue() / a.getWeight(); double rb = b.getValue() / b.getWeight(); double diff = ra - rb; if(diff < 0){ return 1; } else if(diff > 0){ return -1; } else { return 0; } }); return solve(problem, items); }
GreedyForKnapsack { public static boolean[] solveByBestRatioFirst(KnapsackProblem problem){ List<KnapsackProblem.Item> items = problem.getCopyOfItems(); items.sort((a,b) -> { if(a.getWeight() == 0){ return -1; } if(b.getWeight() == 0){ return 1; } double ra = a.getValue() / a.getWeight(); double rb = b.getValue() / b.getWeight(); double diff = ra - rb; if(diff < 0){ return 1; } else if(diff > 0){ return -1; } else { return 0; } }); return solve(problem, items); } }
GreedyForKnapsack { public static boolean[] solveByBestRatioFirst(KnapsackProblem problem){ List<KnapsackProblem.Item> items = problem.getCopyOfItems(); items.sort((a,b) -> { if(a.getWeight() == 0){ return -1; } if(b.getWeight() == 0){ return 1; } double ra = a.getValue() / a.getWeight(); double rb = b.getValue() / b.getWeight(); double diff = ra - rb; if(diff < 0){ return 1; } else if(diff > 0){ return -1; } else { return 0; } }); return solve(problem, items); }  }
GreedyForKnapsack { public static boolean[] solveByBestRatioFirst(KnapsackProblem problem){ List<KnapsackProblem.Item> items = problem.getCopyOfItems(); items.sort((a,b) -> { if(a.getWeight() == 0){ return -1; } if(b.getWeight() == 0){ return 1; } double ra = a.getValue() / a.getWeight(); double rb = b.getValue() / b.getWeight(); double diff = ra - rb; if(diff < 0){ return 1; } else if(diff > 0){ return -1; } else { return 0; } }); return solve(problem, items); }  static boolean[] solveByHeavierFirst(KnapsackProblem problem); static boolean[] solveByLighterFirst(KnapsackProblem problem); static boolean[] solveByBestRatioFirst(KnapsackProblem problem); }
GreedyForKnapsack { public static boolean[] solveByBestRatioFirst(KnapsackProblem problem){ List<KnapsackProblem.Item> items = problem.getCopyOfItems(); items.sort((a,b) -> { if(a.getWeight() == 0){ return -1; } if(b.getWeight() == 0){ return 1; } double ra = a.getValue() / a.getWeight(); double rb = b.getValue() / b.getWeight(); double diff = ra - rb; if(diff < 0){ return 1; } else if(diff > 0){ return -1; } else { return 0; } }); return solve(problem, items); }  static boolean[] solveByHeavierFirst(KnapsackProblem problem); static boolean[] solveByLighterFirst(KnapsackProblem problem); static boolean[] solveByBestRatioFirst(KnapsackProblem problem);  }