Блог

У меня есть X количество деталей с фиксированной стоимостью. Каждая часть имеет N аспектов разной ценности.

Например:

 Part 1: cost = 3,
Width = 10,
Length = 12,
Height = 13,
Weight = 12,
Value = sum of four aspects = 47

Part 2: cost 4,
Width = 20,
Length = 15,
Height = 12,
Weight = 10,
Value = sum of above four aspects = 57

Part 3: cost 2,
Width = 9,
Length = 12,
Height = 9,
Weight = 8,
Value = sum of above four aspects = 38
 

Затем у меня есть много таких разных предметов, например, 20 предметов.
Существует ограничение на максимальное количество предметов, которые я могу выбрать одновременно, например, 8 предметов.
У меня есть ограничение затрат, то есть сумма стоимости выбранных товаров должна быть с заданным пределом, например, 30.

Теперь мне нужно выбрать элементы из этого списка, чтобы получить максимальную ценность. Другим ограничением является то, что в конечном сочетании все аспекты должны быть сбалансированы. например, конечная сумма ширины, длины, высоты и веса должна быть распределена поровну. Если не равны, то, по крайней мере, в сбалансированном диапазоне. т. е. Поскольку существует 4 аспекта, каждый аспект должен составлять около 25% /-5% от общего значения.

Я попытался решить проблему с рюкзаком, но здесь у меня больше измерений.

Один из способов — использовать MILP-модель. Вот простая модель, реализованная в MiniZinc. x это двоичные переменные, представляющие, выбран элемент или нет.

 int: items = 5;
int: selectedItems = 3;
int: maxCost = 10;

set of int: ITEM = 1..items;

array[ITEM] of int: cost = [3, 4, 2, 1, 1];
array[ITEM] of int: width = [10, 20, 9, 15, 12];
array[ITEM] of int: length = [12, 15, 12, 15, 12];
array[ITEM] of int: height = [13, 12, 9, 15, 12];
array[ITEM] of int: weight = [12, 10, 8, 15, 12];
array[ITEM] of int: value = [width[i]   length[i]   height[i]   weight[i] | i in ITEM];
    
array[ITEM] of var 0..1: x;

% selected items constraint
constraint sum(x) <= selectedItems;

% cost constraint
constraint sum(i in ITEM)(cost[i]*x[i]) <= maxCost;

predicate balanced(array[ITEM] of var int: values) =
    let {var int: value = sum(i in ITEM)(values[i]*x[i])} in
    value >= 0.2*totalValue / value <= 0.3*totalValue;

% balance constraints
constraint balanced(width) / balanced(length) / balanced(height) / balanced(weight);

var 1..sum(value): totalValue = sum(i in ITEM)(value[i]*x[i]);

solve maximize totalValue;

output ["totalValue=(totalValue)n"]   
["cost=(sum(i in ITEM)(cost[i]*x[i]))n"]    
["x="]    [show(x)]   
["nratio="]    [show_float(5, 2,sum(i in ITEM)(width[i]*x[i]) / totalValue), show_float(5, 2,sum(i in ITEM)(length[i]*x[i]) / totalValue), show_float(5, 2,sum(i in ITEM)(height[i]*x[i]) / totalValue), show_float(5, 2,sum(i in ITEM)(weight[i]*x[i]) / totalValue)]   
["nvalue="]    [show(value)];
 

Запуск (с решателем Gecode по умолчанию) дает:

 totalValue=165
cost=6
x=[0, 1, 0, 1, 1]
ratio= 0.28 0.25 0.24 0.22
value=[47, 57, 38, 60, 48]