Java:根据某个字段获取大量对象List的最高效组合

Question

我希望在给定一定预算和组合最大限制的情况下最大化星星数量...

示例问题:

预算为 500 欧元，仅访问允许的最多餐厅或更少，用餐并收集尽可能多的星星。

我正在寻求编写一种高效的算法，该算法可能会处理最多 10 个 maxRestaurant 的 100 万个 Restaurant 实例...

有人可以帮忙尝试一下这个问题吗？

注意:这不是家庭作业。我故意将尝试留空，因为我不想影响解决方案的效率

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

  }
}

Answer 1

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

要对其进行建模，请将餐厅的权重 vector 定义为 (price, 1)，其中 price 是该餐厅的用餐价格。限制为(预算，maxRestaurants)，返回为所选餐厅的星级总和。

背包问题及其大多数变体(包括 0-1 背包和多维背包)都是 NP 困难的。这意味着没有已知的算法可以提供准确的答案，同时也可以很好地扩展到大输入大小(例如 1000 万)。