Converting brute force to knapsack – HELP via /r/learnprogramming


Converting brute force to knapsack – HELP

As the title implies, I have a block of code I've written that is incredibly inefficient and I need it converted to use a proper knapsack algorithm instead of this brute force method. If someone could show me the way, I would appreciate it.

Problem: Given a list of items, retrieve the best 20 knapsacks that can be made from them. Constraints: Each knapsack must contain exactly 2 items of type A1/A2, 1 item of type B1, 1 item of type C1, 1 item of type D1, 1 item of type E1, 1 item of type F1 and 3 items of type G1. Each knapsack must weight under 10000.

private static final int TOP_KNAPSACKS = 20; private static final int LIMIT = 10; private static final int MAX_WEIGHT public void buildKnapsacks() { buildKnapsacks(...); } private List<Knapsack> buildKnapsacks(List<Item> items) { List<Item> aList = items.stream() .filter(i -> i.getType() == Type.A1 || i.getType() == Type.A2) .limit(LIMIT) .collect(Collectors.toList()); List<Item> bList = items.stream() .filter(i -> i.getType() == Type.B1) .limit(LIMIT) .collect(Collectors.toList()); List<Item> cList = items.stream() .filter(i -> i.getType() == Type.C1) .limit(LIMIT) .collect(Collectors.toList()); List<Item> dList = items.stream() .filter(i -> i.getType() == Type.D1) .limit(LIMIT) .collect(Collectors.toList()); List<Item> eList = items.stream() .filter(i -> i.getType() == Type.E1) .limit(LIMIT) .collect(Collectors.toList()); List<Item> fList = items.stream() .filter(i -> i.getType() == Type.F1) .limit(LIMIT) .collect(Collectors.toList()); List<Item> gList = items.stream() .filter(i -> i.getType() == Type.G1) .limit(LIMIT) .collect(Collectors.toList()); Knapsack knapsack = new Knapsack(); List<Knapsack> knapsacks = new ArrayList<>(); System.out.println("Brute force starting at " + new Date()); for (Item a1 : aList) { knapsack.setA1(a1); for (Item a2 : aList) { knapsack.setA2(a2); for (Item b1 : bList) { knapsack.setB1(b1); for (Item c1 : cList) { knapsack.setC1(c1); for (Item d1 : dList) { knapsack.setD1(d1); for (Item e1 : eList) { knapsack.setE1(e1); for (Item f1 : fList) { knapsack.setF1(f1); for (Item g1 : gList) { knapsack.setG1(g1); for (Item g2 : gList) { knapsack.setG2(g2); for (Item g3 : gList) { knapsack.setG3(g3); knapsacks = addKnapsack(knapsack, knapsacks); } } } } } } } } } } System.out.println("Completed brute force at " + new Date()); return knapsacks; } private List<Knapsack> addKnapsack(Knapsack knapsack, List<Knapsack> knapsacks) { if (knapsack.weight < MAX_WEIGHT && !knapsacks.contains(knapsack)) { knapsacks.add(new Knapsack(knapsack)); knapsacks.sort(KnapsackUtil.value); while (knapsacks.size() > TOP_KNAPSACKS) { knapsacks.remove(TOP_KNAPSACKS); } } return knapsack; } 

Submitted July 15, 2017 at 05:16PM by Shmua123
via reddit http://ift.tt/2umleiV

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s