优化购物篮的产品分配

Question

我目前面临着设计一种算法来最佳地解决以下任务的挑战：

我们有一组产品，每种产品都与可以放入的特定篮子相关联。例如，猕猴桃可以分配到篮子 1 或 2，而香蕉只能放入篮子 1，依此类推。该算法的目标是将产品划分为尽可能少的篮子，最大的组包含尽可能多的产品。

考虑以下示例：

猕猴桃 - 1, 2
香蕉 - 1
苹果 - 1, 2
菠萝 - 1, 3
椰子 - 2, 3
梅子 - 3

优化的分配涉及将产品隔离如下：
猕猴桃、香蕉、苹果和菠萝被分配到第 1 篮子，
椰子和李子被指定为第 3 篮子。

本质上，挑战是开发一种算法，有效优化产品到篮子的分配，优先考虑最大篮子内产品数量的最大化。

Answer 1

MiniZinc模型可以结合两个目标，找到合适的产品分配到篮子中：

% how many baskets?
int: noOfBaskets = 3;
set of int: Baskets = 1..noOfBaskets;
enum Products =  {Kiwi, Banana, Apple, Pineapple, Coconut, Plum};

%  decision variable: one basket per product
array[Products] of var Baskets: Assignments;

%  which product can be assigned to which baskets?
constraint Assignments[Kiwi] in {1, 2};
constraint Assignments[Banana] in {1};
constraint Assignments[Apple] in {1, 2};
constraint Assignments[Pineapple] in {1, 3};
constraint Assignments[Coconut] in {2, 3};
constraint Assignments[Plum] in {3};

%  an empty basket does not occur in any Assignment
var Baskets: emptyBaskets = 
  sum([sum([Assignments[product] == basket | product in Products]) == 0 | basket in Baskets]);

var 0..card(Products): largestCount = 
  max([sum([Assignments[product] == basket | product in Products]) | basket in Baskets]);

%  objectives are weighted to combine them to a single figure of merit
solve maximize 10*emptyBaskets + 10*largestCount;

结果输出：

Assignments = [Kiwi: 1, Banana: 1, Apple: 1, Pineapple: 1, Coconut: 3, Plum: 3];
_objective = 50;