获取基于字段的大型对象列表的最有效组合
Get the most efficient combination of a large List of objects based on a field
我希望在给定特定预算和组合最大限制的情况下最大限度地增加星星数量。
Example question:
With a budget of 500 euro, visiting only the maximum allowed restaurants or less, dine and collect the most stars possible.
我正在寻找一种高效的算法，它可能会处理最多 10 家餐厅的 100 万个餐厅实例。
请注意，这是我昨天提出的一个问题的交叉 post：
Java: Get the most efficient combination of a large List of objects based on a field
下面的解决方案会给r8餐厅每颗星分配15$，这意味着在生成列表时，它首先将其放入列表，剩下的70$只能得到2更多的星星给了总共 4 颗星。然而，如果它足够聪明而跳过了 r8 餐厅（即使它是每星级最高的美元比率），r1 餐厅实际上是一个更好的预算选择，因为它的成本为 100 美元，而且5 颗星。
任何人都可以帮助尝试这个问题并击败当前的解决方案吗？
import itertools
class Restaurant():
def __init__(self, cost, stars):
self.cost = cost
self.stars = stars
self.ratio = cost / stars
def display(self):
print("Cost: $" + str(self.cost))
print("Stars: " + str(self.stars))
print()
r1 = Restaurant(100, 5)
r2 = Restaurant(140, 3)
r3 = Restaurant(90, 4)
r4 = Restaurant(140, 3)
r5 = Restaurant(120, 4)
r6 = Restaurant(60, 1)
r7 = Restaurant(40, 1)
r8 = Restaurant(30, 2)
r9 = Restaurant(70, 2)
r10 = Restaurant(250, 5)
print()
print("***************")
print("** Unsorted: **")
print("***************")
print()
restaurants = [r1, r2, r3, r4, r5, r6, r7, r8, r9, r10]
for restaurant in restaurants:
print(restaurant.ratio, restaurant.stars)
print()
print("***************")
print("** Sorted: **")
print("***************")
print()
sorted_restaurants = sorted(restaurants, key = lambda x: x.ratio, reverse = True)
for restaurant in sorted_restaurants:
print(restaurant.ratio, restaurant.stars)
print()
print("*********************")
print("** Begin Rucksack: **")
print("*********************")
print()
max = 5
budget = 100
spent = 0
quantity = 0
rucksack = []
for i in itertools.count():
if len(rucksack) >= max or i == len(sorted_restaurants):
break
sorted_restaurants[i].display()
if sorted_restaurants[i].cost + spent <= budget:
spent = spent + sorted_restaurants[i].cost
rucksack.append(sorted_restaurants[i])
print("Total Cost: $" + str(sum([x.cost for x in rucksack])))
print("Total Stars: " + str(sum([x.stars for x in rucksack])))
print()
print("*****************")
print("** Final List: **")
print("*****************")
print()
for restaurant in rucksack:
restaurant.display()
听起来您的问题与背包问题几乎相同：在给定特定重量和体积限制的情况下最大化价值。基本上价值=总星数，重量=价格，背包限制=总预算。现在有总 "items"（餐厅访问）的额外限制，但这并没有改变要点。
你可能知道也可能不知道，背包问题是 NP 难的，这意味着没有已知的具有多项式时间缩放的算法。
不过，可能存在使用动态规划的高效伪多项式算法，当然也有高效的启发式算法，例如您似乎已经发现的 "greedy" 启发式算法。这种启发式涉及首先开始填充最高的 "density" 项（每美元最多的星星）。如您所见，这种启发式方法在某些情况下无法找到真正的最优值。
动态规划方法在这里应该很不错。它基于递归：给定预算 B 和剩余访问次数 V，在一组餐厅 R 中，最适合光顾的一组餐厅是什么？
看这里：https://en.wikipedia.org/wiki/Knapsack_problem#0/1_knapsack_problem
基本上我们为"max stars"定义了一个数组m，其中
m[i, b, v] 是允许我们访问最多（包括）餐厅编号 i、最多消费 b、最多访问 v 家餐厅（上限）。
现在，我们自下而上填充这个数组。例如，
m[0, b, v] = 0 对于 b 和 v 的所有值，因为如果我们不能去任何餐馆，我们就无法获得任何星星。
此外，m[i, b, 0] = 0 用于 i 和 b 的所有值，因为如果我们用完所有访问次数，我们将无法获得更多的星星。
下一行也不难：
m[i, b, v] = m[i - 1, b, v] if p[i] > b
其中 p[i] 是在餐厅 i 用餐的价格。这条线说什么？好吧，如果餐厅 i 比我们剩下的钱 (b) 贵，那么我们就不能去那里了。这意味着无论我们包括最多 i 还是最多 i - 1.
的餐厅，我们可以获得的最大星星数量是相同的
下一行有点棘手：
m[i, b, v] = max(m[i-1, b, v]), m[i-1, b - p[i], v-1] + s[i]) if p[i] <= b
呸。 s[i] 是您从餐厅获得的星星数量 i 顺便说一句。
这句话说的是什么？它是动态规划方法的核心。考虑到我们在查看最多 i 的餐厅时可以获得的最大星数，那么在最终的解决方案中，我们要么去那里，要么不去，我们 "just" 必须看看哪个这两条路径通向更多的星星：
如果我们不去餐厅 i，那么我们将保持相同的金额和剩余访问量。我们在这条路径上可以获得的最大星星数量与我们甚至没有看餐厅 i 一样。这是 max 中的第一部分。
但如果我们真的去餐厅 i，那么我们的钱就会少 p[i]，光顾次数会少，而星星会多 s[i]。这是 max.
的第二部分
现在问题很简单：两者中哪个更大。
您可以创建此数组并使用相对简单的 for 循环填充它（从 wiki 获取灵感）。不过，这只是为您提供了星级数量，而不是实际的餐厅列表。为此，在 w 的计算中添加一些额外的簿记。
我希望这些信息足以让您朝着正确的方向前进。
或者，您可以根据二进制变量和二次 objective 函数编写您的问题，并在 D-Wave 量子退火器上解决它：-p 如果您想了解更多信息，请给我发消息。
使用与相同的想法：
In a collection of n positive numbers that sum up to S, at least one of them will be less than S divided by n (S/n)
您可以从潜在的 "cheapest" 家餐厅.
开始构建列表
算法步骤：
- 找到成本 < 500 / 10 的 5 家餐厅，每家餐厅的星级 不同 并且每个星级的 成本最低 。例如 r1、r2、r3、r4、r5
- 对于上述每个值，找到另外 5 家成本 < (500 - cost(x)) / 9 且 不同星级 的餐厅。同样 select 每颗星的最低成本
- 这样做，直到您达到 10 家餐厅并且您不超过 预算。
- 为 1 - 9 家餐厅限制重新运行上述 3 个步骤。
- 保留产生最多星星的解决方案
当然，您不能重新select一家餐馆。
我认为最坏的情况，你将不得不计算 5x5x5... = 5^10 + 5^9 + ... + 5^2 + 5（= 约 1200 万）个解决方案。
在javascript
function Restaurant(name, cost, stars) {
this.name = name;
this.cost = cost;
this.stars = stars;
}
function RestaurantCollection() {
var restaurants = [];
var cost = 0;
this.stars = 0;
this.addRestaurant = function(restaurant) {
restaurants.push(restaurant);
cost += restaurant.cost;
this.stars += restaurant.stars;
};
this.setRestaurants = function(clonedRestaurants, nCost, nStars) {
restaurants = clonedRestaurants;
cost = nCost;
this.stars += nStars;
};
this.getAll = function() {
return restaurants;
};
this.getCost = function() {
return cost;
};
this.setCost = function(clonedCost) {
cost = clonedCost;
};
this.findNext5Restaurants = function(restaurants, budget, totalGoal) {
var existingRestaurants = this.getAll();
var maxCost = (budget - cost) / (totalGoal - existingRestaurants.length);
var cheapestRestaurantPerStarRating = [];
for(var stars = 5; stars > 0; stars--) {
var found = findCheapestRestaurant(restaurants, stars, maxCost, existingRestaurants);
if(found) {
cheapestRestaurantPerStarRating.push(found);
}
}
return cheapestRestaurantPerStarRating;
};
this.clone = function() {
var restaurantCollection = new RestaurantCollection();
restaurantCollection.setRestaurants([...restaurants], this.getCost(), this.stars);
return restaurantCollection;
};
}
function findCheapestRestaurant(restaurants, stars, maxCost, excludeRestaurants) {
var excludeRestaurantNames = excludeRestaurants.map(restaurant => restaurant.name);
var found = restaurants.find(restaurant => restaurant.stars == stars && restaurant.cost <= maxCost && !excludeRestaurantNames.includes(restaurant.name));
return found;
}
function calculateNextCollections(restaurants, collections, budget, totalGoal) {
var newCollections = [];
collections.forEach(collection => {
var nextRestaurants = collection.findNext5Restaurants(restaurants, budget, totalGoal);
nextRestaurants.forEach(restaurant => {
var newCollection = collection.clone();
newCollection.addRestaurant(restaurant);
if(newCollection.getCost() <= budget) {
newCollections.push(newCollection);
}
});
});
return newCollections;
};
var restaurants = [];
restaurants.push(new Restaurant('r1', 100, 5));
restaurants.push(new Restaurant('r2',140, 3));
restaurants.push(new Restaurant('r3',90, 4));
restaurants.push(new Restaurant('r4',140, 3));
restaurants.push(new Restaurant('r5',120, 4));
restaurants.push(new Restaurant('r6',60, 1));
restaurants.push(new Restaurant('r7',40, 1));
restaurants.push(new Restaurant('r8',30, 2));
restaurants.push(new Restaurant('r9',70, 2));
restaurants.push(new Restaurant('r10',250, 5));
restaurants.sort((a, b) => a.cost - b.cost);
var max = 5;
var budget = 100;
var total = max;
var totalCollections = [];
for(var totalGoal = total; totalGoal > 0; totalGoal--) {
var collections = [new RestaurantCollection()];
for(var i = totalGoal; i > 0; i--) {
collections = calculateNextCollections(restaurants, collections, budget, totalGoal);
}
totalCollections = totalCollections.concat(collections);
}
var totalCollections = totalCollections.map(collection => {
return {
name: collection.getAll().map(restaurant => restaurant.name),
stars: collection.stars,
cost: collection.getCost()
}
});
console.log("Solutions found:\n");
console.log(totalCollections);
totalCollections.sort((a, b) => b.stars - a.stars);
console.log("Best solution:\n");
console.log(totalCollections[0]);
我希望在给定特定预算和组合最大限制的情况下最大限度地增加星星数量。
Example question:
With a budget of 500 euro, visiting only the maximum allowed restaurants or less, dine and collect the most stars possible.
我正在寻找一种高效的算法，它可能会处理最多 10 家餐厅的 100 万个餐厅实例。
请注意，这是我昨天提出的一个问题的交叉 post： Java: Get the most efficient combination of a large List of objects based on a field
下面的解决方案会给r8餐厅每颗星分配15$，这意味着在生成列表时，它首先将其放入列表，剩下的70$只能得到2更多的星星给了总共 4 颗星。然而，如果它足够聪明而跳过了 r8 餐厅（即使它是每星级最高的美元比率），r1 餐厅实际上是一个更好的预算选择，因为它的成本为 100 美元，而且5 颗星。
任何人都可以帮助尝试这个问题并击败当前的解决方案吗？
import itertools
class Restaurant():
def __init__(self, cost, stars):
self.cost = cost
self.stars = stars
self.ratio = cost / stars
def display(self):
print("Cost: $" + str(self.cost))
print("Stars: " + str(self.stars))
print()
r1 = Restaurant(100, 5)
r2 = Restaurant(140, 3)
r3 = Restaurant(90, 4)
r4 = Restaurant(140, 3)
r5 = Restaurant(120, 4)
r6 = Restaurant(60, 1)
r7 = Restaurant(40, 1)
r8 = Restaurant(30, 2)
r9 = Restaurant(70, 2)
r10 = Restaurant(250, 5)
print()
print("***************")
print("** Unsorted: **")
print("***************")
print()
restaurants = [r1, r2, r3, r4, r5, r6, r7, r8, r9, r10]
for restaurant in restaurants:
print(restaurant.ratio, restaurant.stars)
print()
print("***************")
print("** Sorted: **")
print("***************")
print()
sorted_restaurants = sorted(restaurants, key = lambda x: x.ratio, reverse = True)
for restaurant in sorted_restaurants:
print(restaurant.ratio, restaurant.stars)
print()
print("*********************")
print("** Begin Rucksack: **")
print("*********************")
print()
max = 5
budget = 100
spent = 0
quantity = 0
rucksack = []
for i in itertools.count():
if len(rucksack) >= max or i == len(sorted_restaurants):
break
sorted_restaurants[i].display()
if sorted_restaurants[i].cost + spent <= budget:
spent = spent + sorted_restaurants[i].cost
rucksack.append(sorted_restaurants[i])
print("Total Cost: $" + str(sum([x.cost for x in rucksack])))
print("Total Stars: " + str(sum([x.stars for x in rucksack])))
print()
print("*****************")
print("** Final List: **")
print("*****************")
print()
for restaurant in rucksack:
restaurant.display()
听起来您的问题与背包问题几乎相同：在给定特定重量和体积限制的情况下最大化价值。基本上价值=总星数，重量=价格，背包限制=总预算。现在有总 "items"（餐厅访问）的额外限制，但这并没有改变要点。
你可能知道也可能不知道，背包问题是 NP 难的，这意味着没有已知的具有多项式时间缩放的算法。
不过，可能存在使用动态规划的高效伪多项式算法，当然也有高效的启发式算法，例如您似乎已经发现的 "greedy" 启发式算法。这种启发式涉及首先开始填充最高的 "density" 项（每美元最多的星星）。如您所见，这种启发式方法在某些情况下无法找到真正的最优值。
动态规划方法在这里应该很不错。它基于递归：给定预算 B 和剩余访问次数 V，在一组餐厅 R 中，最适合光顾的一组餐厅是什么？
看这里：https://en.wikipedia.org/wiki/Knapsack_problem#0/1_knapsack_problem
基本上我们为"max stars"定义了一个数组m，其中
m[i, b, v] 是允许我们访问最多（包括）餐厅编号 i、最多消费 b、最多访问 v 家餐厅（上限）。
现在，我们自下而上填充这个数组。例如，
m[0, b, v] = 0 对于 b 和 v 的所有值，因为如果我们不能去任何餐馆，我们就无法获得任何星星。
此外，m[i, b, 0] = 0 用于 i 和 b 的所有值，因为如果我们用完所有访问次数，我们将无法获得更多的星星。
下一行也不难：
m[i, b, v] = m[i - 1, b, v] if p[i] > b
其中 p[i] 是在餐厅 i 用餐的价格。这条线说什么？好吧，如果餐厅 i 比我们剩下的钱 (b) 贵，那么我们就不能去那里了。这意味着无论我们包括最多 i 还是最多 i - 1.
下一行有点棘手：
m[i, b, v] = max(m[i-1, b, v]), m[i-1, b - p[i], v-1] + s[i]) if p[i] <= b
呸。 s[i] 是您从餐厅获得的星星数量 i 顺便说一句。
这句话说的是什么？它是动态规划方法的核心。考虑到我们在查看最多 i 的餐厅时可以获得的最大星数，那么在最终的解决方案中，我们要么去那里，要么不去，我们 "just" 必须看看哪个这两条路径通向更多的星星：
如果我们不去餐厅 i，那么我们将保持相同的金额和剩余访问量。我们在这条路径上可以获得的最大星星数量与我们甚至没有看餐厅 i 一样。这是 max 中的第一部分。
但如果我们真的去餐厅 i，那么我们的钱就会少 p[i]，光顾次数会少，而星星会多 s[i]。这是 max.
现在问题很简单：两者中哪个更大。
您可以创建此数组并使用相对简单的 for 循环填充它（从 wiki 获取灵感）。不过，这只是为您提供了星级数量，而不是实际的餐厅列表。为此，在 w 的计算中添加一些额外的簿记。
我希望这些信息足以让您朝着正确的方向前进。
或者，您可以根据二进制变量和二次 objective 函数编写您的问题，并在 D-Wave 量子退火器上解决它：-p 如果您想了解更多信息，请给我发消息。
使用与
In a collection of n positive numbers that sum up to S, at least one of them will be less than S divided by n (S/n)
您可以从潜在的 "cheapest" 家餐厅.
开始构建列表算法步骤：
- 找到成本 < 500 / 10 的 5 家餐厅，每家餐厅的星级 不同 并且每个星级的 成本最低 。例如 r1、r2、r3、r4、r5
- 对于上述每个值，找到另外 5 家成本 < (500 - cost(x)) / 9 且 不同星级 的餐厅。同样 select 每颗星的最低成本
- 这样做，直到您达到 10 家餐厅并且您不超过 预算。
- 为 1 - 9 家餐厅限制重新运行上述 3 个步骤。
- 保留产生最多星星的解决方案
当然，您不能重新select一家餐馆。
我认为最坏的情况，你将不得不计算 5x5x5... = 5^10 + 5^9 + ... + 5^2 + 5（= 约 1200 万）个解决方案。
在javascript
function Restaurant(name, cost, stars) {
this.name = name;
this.cost = cost;
this.stars = stars;
}
function RestaurantCollection() {
var restaurants = [];
var cost = 0;
this.stars = 0;
this.addRestaurant = function(restaurant) {
restaurants.push(restaurant);
cost += restaurant.cost;
this.stars += restaurant.stars;
};
this.setRestaurants = function(clonedRestaurants, nCost, nStars) {
restaurants = clonedRestaurants;
cost = nCost;
this.stars += nStars;
};
this.getAll = function() {
return restaurants;
};
this.getCost = function() {
return cost;
};
this.setCost = function(clonedCost) {
cost = clonedCost;
};
this.findNext5Restaurants = function(restaurants, budget, totalGoal) {
var existingRestaurants = this.getAll();
var maxCost = (budget - cost) / (totalGoal - existingRestaurants.length);
var cheapestRestaurantPerStarRating = [];
for(var stars = 5; stars > 0; stars--) {
var found = findCheapestRestaurant(restaurants, stars, maxCost, existingRestaurants);
if(found) {
cheapestRestaurantPerStarRating.push(found);
}
}
return cheapestRestaurantPerStarRating;
};
this.clone = function() {
var restaurantCollection = new RestaurantCollection();
restaurantCollection.setRestaurants([...restaurants], this.getCost(), this.stars);
return restaurantCollection;
};
}
function findCheapestRestaurant(restaurants, stars, maxCost, excludeRestaurants) {
var excludeRestaurantNames = excludeRestaurants.map(restaurant => restaurant.name);
var found = restaurants.find(restaurant => restaurant.stars == stars && restaurant.cost <= maxCost && !excludeRestaurantNames.includes(restaurant.name));
return found;
}
function calculateNextCollections(restaurants, collections, budget, totalGoal) {
var newCollections = [];
collections.forEach(collection => {
var nextRestaurants = collection.findNext5Restaurants(restaurants, budget, totalGoal);
nextRestaurants.forEach(restaurant => {
var newCollection = collection.clone();
newCollection.addRestaurant(restaurant);
if(newCollection.getCost() <= budget) {
newCollections.push(newCollection);
}
});
});
return newCollections;
};
var restaurants = [];
restaurants.push(new Restaurant('r1', 100, 5));
restaurants.push(new Restaurant('r2',140, 3));
restaurants.push(new Restaurant('r3',90, 4));
restaurants.push(new Restaurant('r4',140, 3));
restaurants.push(new Restaurant('r5',120, 4));
restaurants.push(new Restaurant('r6',60, 1));
restaurants.push(new Restaurant('r7',40, 1));
restaurants.push(new Restaurant('r8',30, 2));
restaurants.push(new Restaurant('r9',70, 2));
restaurants.push(new Restaurant('r10',250, 5));
restaurants.sort((a, b) => a.cost - b.cost);
var max = 5;
var budget = 100;
var total = max;
var totalCollections = [];
for(var totalGoal = total; totalGoal > 0; totalGoal--) {
var collections = [new RestaurantCollection()];
for(var i = totalGoal; i > 0; i--) {
collections = calculateNextCollections(restaurants, collections, budget, totalGoal);
}
totalCollections = totalCollections.concat(collections);
}
var totalCollections = totalCollections.map(collection => {
return {
name: collection.getAll().map(restaurant => restaurant.name),
stars: collection.stars,
cost: collection.getCost()
}
});
console.log("Solutions found:\n");
console.log(totalCollections);
totalCollections.sort((a, b) => b.stars - a.stars);
console.log("Best solution:\n");
console.log(totalCollections[0]);