Java：根据字段获取大对象列表的最有效组合

Question

我正在考虑在给定特定stars的情况下最大化budget的数量，并在组合上设置最大限制...

示例问题：

预算为500欧元，只参观允许的最大餐厅或以下餐厅，用餐并收集最多的星星。

我正在寻找一种有效的算法，该算法可能最多处理10个Restaurant中的一百万个maxRestaurants实例>]

任何人都可以帮助解决该问题吗？

注意：这不是家庭作业。我故意不做任何尝试，因为我不想影响解决方案的效率

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

  }
}

我正在考虑在给定的预算和组合上的最大限制的情况下最大化星级数量...示例问题：如果预算为500欧元，则仅访问允许的最大餐厅或...]]

Answer 1

这是multidimensional 0-1 knapsack problem的一个实例。

[要这样建模，请将餐厅的权重矢量定义为(price, 1)，其中price是该餐厅的用餐价格。限制为(budget, maxRestaurants)，收益为所选餐厅的stars之和。