根据款式要点和成本优化服装选择

Question

考虑到以下几点，你将如何在保持最大成本的情况下优化“风格点”？你必须从每一类中取出一件物品，并从“配件”类中取出两件单独的物品。

costlimit=100

类别:项目：(样式点，成本)

裤子:牛仔裤：(5，25)，卡其布：(3，15)，短裤：(2，10)顶部: tshirt1:(5，28)，tshirt2:(4，20)，tshirt3:(2，10)鞋子: shoes1:(8，50)，shoes2:(4,30)，shoes3:(2,15)配件: Acc1:(1,5)，Acc2:(1，4)，Acc3:(2,6)，Acc4:(3，9)，Acc5:(4,15)

我试图找到这个问题的名字，我想这是0-1背包问题的一个旋转。

Answer 1

这是一个最优化问题，也许你想要线性代数。

Answer 2

这类问题可以使用MiniZinc之类的约束求解器进行建模和解决。

我的尝试：：

int: Jeans   = 1;
int: Khakis  = 2;
int: Shorts  = 3;
int: Tshirt1 = 4;
int: Tshort2 = 5;
int: Tshirt3 = 6;
int: Shoes1  = 7;
int: Shoes2  = 8;
int: Shoes3  = 9;
int: Acc1    = 10;
int: Acc2    = 11;
int: Acc3    = 12;
int: Acc4    = 13;
int: Acc5    = 14;

set of int: Items = Jeans .. Acc5;
set of int: Pants = Jeans .. Shorts;
set of int: Tops = Tshirt1 .. Tshirt3;
set of int: Shoes = Shoes1 .. Shoes3;
set of int: Accessories = Acc1 .. Acc5;

array[Items] of int: Costs;
array[Items] of int: StylePoints;
array[Items] of string: Names;

int: Costlimit = 100;
Costs       = [25,15,10,28,20,10,50,30,15, 5, 4, 6, 9,15];
StylePoints = [5 , 3, 2, 5, 4, 2, 8, 4, 2, 1, 1, 2, 3, 4];
Names = ["Jeans","Khakis","Shorts",
         "Tshirt1","Tshort2","Tshirt3",
         "Shoes1","Shoes2","Shoes3",
         "Acc1","Acc2","Acc3","Acc4","Acc5"];

array[Items] of var 0 .. 1: Select;

%%  take 1 item from each class
constraint 
    1 = sum(i in Pants)(Select[i]);

constraint 
    1 = sum(i in Tops)(Select[i]);

constraint 
    1 = sum(i in Shoes)(Select[i]);

%%  take 2 separate items from accessories
constraint 
    2 = sum(i in Accessories)(Select[i]);

%%  stay in budget
constraint
    Costlimit >= sum(i in Items)(Select[i] * Costs[i]);

%%  maximize style points
solve maximize 
    sum (i in Items) (Select[i] * StylePoints[i]);

%
%  Output solution as table of variable value assignments
%%
output 
["\nSelected items:"] ++
["\n" ++ show(Names[i]) ++ ": " 
      ++ show(Select[i]) 
      ++ "( style " ++ show(StylePoints[i]) 
      ++ "; cost " ++ show(Costs[i]) ++ ")" | i in Items] ++
["\n"] ++
["\nCosts:        " ++ show(sum(i in Items)(Select[i] * Costs[i]))] ++
["\nStyle points: " ++ show(sum(i in Items)(Select[i] * StylePoints[i]))];

我使用了一个[0..1]整数数组作为决策变量。如果选择了相应的项，则数组元素为1。否则为0。MiniZinc能够找到满足所有给定约束并最大化目标值的解决方案。

生成的解决方案：

Selected items:
Jeans: 1( style 5; cost 25)
Khakis: 0( style 3; cost 15)
Shorts: 0( style 2; cost 10)
Tshirt1: 0( style 5; cost 28)
Tshort2: 0( style 4; cost 20)
Tshirt3: 1( style 2; cost 10)
Shoes1: 1( style 8; cost 50)
Shoes2: 0( style 4; cost 30)
Shoes3: 0( style 2; cost 15)
Acc1: 0( style 1; cost 5)
Acc2: 0( style 1; cost 4)
Acc3: 1( style 2; cost 6)
Acc4: 1( style 3; cost 9)
Acc5: 0( style 4; cost 15)

Costs:        100
Style points: 20