Java：基于字段获取大型对象列表的最有效组合 [英] Java: Get the most efficient combination of a large List of objects based on a field

问题描述

鉴于特定的预算和组合的最大限制，我希望最大限度地增加个明星的数量。 ..

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

示例问题：

预算为500欧元，仅访问允许的最大值

我正在寻找一种有效的算法，该算法可能处理100万个 Restaurant 个实例，最多可容纳10个 maxRestaurants ...

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

任何人都可以

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

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

  }
}

推荐答案

这是多维0-1背包问题。

要对其进行建模，请将餐厅的权重矢量定义为 （price，1），其中 price 是在该餐厅用餐的价格。限制为（预算，maxRestaurants），收益为所选餐厅中星的总和。

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.

背包问题以及包括0-1背包和多维背包在内的大多数背包都是NP-hard。这意味着没有已知的算法能够给出准确的答案，同时还可以很好地扩展到较大的输入大小（例如1000万）。

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).

这篇关于Java：基于字段获取大型对象列表的最有效组合的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！