Java: Get the most efficient combination of a large List of objects based on a field

Question

I'm looking to maximise the number of stars given a certain budget and max limit on the combination...

Example question:

With a budget of 500 euro, visiting only the maximum allowed restaurants or less, dine and collect the most stars possible.

I'm looking to write an efficient algorithm, that could potentially process 1 million Restaurant instances for up to 10 maxRestaurants...

Can anyone help attempt the problem?

Note: This is not homework. I intentionally left the attempt empty as I don't want to influence the efficiency of the solution

Restaurant.java

public class Restaurant {
  double cost;
  int stars;

  public Restaurant(double cost, int stars) {
    this.cost = cost;
    this.stars = stars;
  }
}

Main.java

import java.util.List;
import java.util.Arrays;

class Main {

  public static void main(String[] args) {
    Restaurant r1 = new Restaurant(100.0, 5);
    Restaurant r2 = new Restaurant(20.0, 1);
    Restaurant r3 = new Restaurant(75.0, 3);
    Restaurant r4 = new Restaurant(125.0, 4);
    Restaurant r5 = new Restaurant(60.0, 2);
    Restaurant r6 = new Restaurant(80.0, 4);
    Restaurant r7 = new Restaurant(40.0, 1);
    Restaurant r8 = new Restaurant(200.0, 3);
    Restaurant r9 = new Restaurant(120.0, 3);
    Restaurant r10 = new Restaurant(50.0, 2);

    List<Restaurant> restaurants = 
        Arrays.asList(r1, r2, r3, r4, r5, r6, r7, r8, r9, r10);

    double budget;
    int maxRestaurants;

    budget = 500.0;
    maxRestaurants = 1;
    // { r1 } -- 5 stars

    budget = 200;
    maxRestaurants = 2;
    // { r1, r6 } -- 9 stars

    budget = 500;
    maxRestaurants = 5;
    // { r1, r4, r6, r3, r9 } -- 19 stars

    budget = 200;
    maxRestaurants = 10;
    // { r1, r6, r2 } -- 10 stars

  }
}

Notability

you could sort the list in stars/cost order and use them in your result that order, if under the budget – Lacielacing

Thats actually how I drafted up the potential commented outputs... interesting how I never actually thought to implement the solution that way. Thanks ! – Notability

Hey @bohemian, I've made an attempt (using Python because it's easier) and reposted this question over here: #59094639 There is an issue with the solution if you take a look here: repl.it/repls/DelayedCulturedAbility - I wonder if you can take a look? The issue is that, based on the stars / cost, the order means that once some values are added, the bigger ones may cross the budget limit even though they would have been the optimal solution (100 is 5 stars in the example) – Notability

firstly, my suggestion may not find the optimal solution, but it is much simpler and will probably find an acceptable good solution. Now you could refine the sort order by first comparing stars/cost and if that value is equal, then order by the number of stars greatest first. – Lacielacing

Answer 1

This is an instance of the multidimensional 0-1 knapsack problem.

To model it as such, define the weight vector of a restaurant as (price, 1) where price is the price of dining at that restaurant. The limits are (budget, maxRestaurants), and the payoff is the sum of stars over the restaurants chosen.

The knapsack problem, and most variants of it including 0-1 knapsack and multidimensional knapsack, are NP-hard. This means no known algorithm gives exact answers while also scaling well to large input sizes (such as 10 million).

Toothpaste

Thank you for this! This definitely will help search a solution. – Notability