优化问题，显示给定一组选择的最大剩余选项数 [英] Optimization problem, showing maximum number of remaining options given a collection of selections

问题描述

我的代码解决方案目前没有涵盖所有可能性，而且是半成品......寻求帮助完成！

背景

我有一个包含任意数量属性的苹果篮子，以及这些属性的可能选项.例如，假设我选择定义的 3 个属性以及可能的选项是:

- 价格:[1, 2, 5]- 尺寸:[S、M、L]- 颜色:[红、绿、黄]

换句话说，上面说有 3 种可能的价格、3 种可能的尺寸、3 种可能的颜色来描述我篮子里的苹果.但是，没有关于数量的信息.

例如，这个篮子可以由 3 个不同的苹果组成:

- 1 美元，小红苹果- 2 美元，中等，青苹果- 5 美元，大黄苹果

或者它可以由 12 个苹果组成:

- 3 $1，小红苹果- 2 个 1 美元，小青苹果- 2 个 2 美元，中等，青苹果- 4 个 5 美元，中等黄苹果- 1 个 5 美元，大红苹果

一个重要的思考方式是，如果我要推销这篮苹果，我想推销它以提供最大数量的选项(对于我选择定义的属性))，无论这些选项存在多少计数.在最后一个例子中，一篮子 12 个苹果，我想推销我有一个 large-size 和一个 red-color 即使这两个选项出现在一个单个给定的苹果.

问题

鉴于这样的营销策略，当一个人订购一个苹果时，我想给他们满足他们要求的苹果，同时对我的篮子中其余部分的适销性的限制最小.这两个是彼此的倒数.就我而言，我感兴趣的是计算他们拿走苹果后剩余选项的最大数量(而不是计算他们应该拿走哪个苹果).

上述 12 个苹果篮子场景中的 3 个示例.

1. 如果有人订购一个 5 美元的苹果，我肯定想给他们一个中等黄色的苹果，而不是一个大的红苹果，因为一旦我送出我的大红苹果，大尺寸 和 red-color 从我拥有的可销售选项中永久删除.

2. 然而，如果有人点了一个 5 美元的红苹果，那么唉，我不得不放弃我唯一的大红苹果，因此我失去了 large-size 和 red-color 来自可销售选项列表

3. 如果有人点了一个 5 美元的苹果(上面的例子 1)，然后第二个人点了一个大苹果，我又一次失去了 large-size 和 red-color

方法的伪代码 &输出:

def resume_options(order);结尾# 篮子 = 12 个苹果对象，如上述示例场景中所定义### 示例 1bag.remaining_options([{价格:5}])=>{价格:[1, 2, 5],尺码: [S, M, L],颜色:【红、绿、黄】}bag.remaining_options([{价格:5，颜色:红色}])=>{价格:[1, 2, 5],尺码: [S, M],颜色:[绿色，黄色]}bag.remaining_options([{price:5}, {size: large}])=>{价格:[1, 2, 5],尺码: [S, M],颜色:【绿、黄】}

我的解决方案

只是玩弄上面的例子，当有人订购时，我想到了两种可能的选择.

1. 他们的订单可能足够严格(例如，他们使用多个属性进行订单)，以至于他们只能获得 1 个苹果.在这种情况下，该特定苹果的所有属性都会从可销售列表中扣除.
2. 它们的顺序可以是松散定义的(例如，它们对一个属性进行排序).在这种情况下，仅从可销售列表中扣除已订购的属性

这是我的解决方案

<预><代码># 假设篮子里的每个苹果都有一个模型苹果，其中定义的属性是模型对象本身的属性# 并且其中 apples = 上述 12 个苹果的篮子定义剩余选项(顺序)# 首先，为定义的属性构建所有篮子选项的计数；count 是相互独立的，因为我们正在最大化选项defined_attributes = [:price, :size, :color]剩余选项 = {}defined_attributes.each 做 |a|剩余选项[a] = apples.group(key).count结尾# 结果# 剩余选项 = {# 价格:{1=>2, 2=>1, 5=>1},# 尺寸:{S"=>2，M"=>2，L"=>1}，# 颜色:{红色"=>2，绿色"=>2，黄色"=>1}# }order.each 做 |o|matched_apples_from_basket = apples.where(o)如果matched_apples_from_basket.size == 1# 这1个苹果的所有属性必须非独立减去；这是一个容量限制匹配的苹果 = 匹配的苹果_from_basket.lastleft_options.each do |option, count_hash|剩余选项[选项][matched_apple.send(选项)] -= 1结尾别的# 松散约束，我们仍然可以独立扣除o.each do |option, value|剩余选项[选项][值] -= 1结尾结尾结尾left_options.each do |option, count_hash|剩余选项[选项] = count_hash.reject { |v, 计数|计数＜1 }.keys结尾返回剩余选项结尾

虽然这个解决方案在我提到的测试示例场景中确实有效(任何错误都是糟糕的复制工作......希望很小，抱歉)，因为查询独立运行在每个订购的项目上，当订购的集合时这会失败项目本身会导致约束.

例如，如果订单如下所示:[{price:"5"},{price:"5"},{price:"5"},{price:"5"};},{price:5"}]，我的解决方案将独立处理每个查询，并且独立地，$5 不是容量限制.所以我的解决方案会从独立的选项集中减去 5 美元，这样在最后，你会有一组剩余的 {price:[1,2],size:["Small","Medium",大号"]，颜色:[红色"、绿色"、黄色"]}

但这将是错误的，因为总的来说，订购 5 个 5 美元的苹果意味着您将所有的苹果都拿走，这会造成容量限制，因为现在将不再有黄色或大苹果.所以结果实际上应该是 {price:[1,2],size:[Small",Medium"], color: [Red", Green"]}

解决方案

假设我们有一个哈希数组，如下所示:

篮子 = [{价格:1，尺寸::S，颜色::红色，数量:3}，{ 价格:1，尺寸::S，颜色::绿色，数量:2}，{价格:2，尺寸::M，颜色::绿色，数量:2}，{ 价格:4，尺码::M，颜色::粉红色，数量:0}，{ 价格:5，尺码::M，颜色::黄色，数量:4}，{ 价格:5，尺寸::L，颜色::红色，数量:1}，]

这对应于问题中给出的示例之一，但有一个变化:我添加了价值 4 美元的中等大小的粉红色苹果，其现有数量为零.我这样做的原因会很清楚.

我们可以计算以下内容:

def 属性(篮子)bag.each_with_object({}) 做 |g,h|g.each do |attr,value|h[attr] = Hash.new(0) 除非 h.key?(attr)h[attr][value] += g[:qty] 除非 attr == :qty结尾结尾结尾

attr = 属性(篮子)#=>{:价格=>{1=>5, 2=>2, 4=>0, 5=>5},# :size=>{:S=>5, :M=>6, :L=>1},# :color=>{:red=>4, :green=>4, :pink=>0, :yellow=>4}}

例如，有6个苹果，大小为:M:

篮子[2][:数量] + 篮子[3][:数量] + 篮子[4][:数量]#=>2 + 0 + 4 = 6

见Hash::new<的形式/a> 接受一个参数(默认值，这里是 0)并且没有块.如果 h = Hash.new(0) 然后 h[k] 返回默认值 0 如果 h 没有键 >k.例如，最初 h 没有键，所以 h['cat'] 返回 0(并且不会改变 h).如果我们设置h['cat'] = 9，那么当然h['cat']返回9，因为h 现在有一个键 'cat'.

---

我们对任何此类散列attributes(basket)的多样性度量可能如下.

def 多样性(属性)属性.sum { |_,g|g.count { |_,cnt|cn>0 } }结尾

attributes 的键值对之一是

:color=>{:red=>4, :green=>4, :pink=>0, :yellow=>4}}

当这个键值对被传递给sum的块时，块变量被设置为1:

_ #=>:颜色g#=>{:red=>4, :green=>4, :pink=>0, :yellow=>4}

块计算仅计算 g 大于零的值的数量.

对于这个特定的篮子:

多样性(属性)#=>9

现在假设使用以下属性集之一请求苹果，我将其称为要求:

{},{价格:1}，{价格:2}，{价格:5}，{ 大小: :S }, { 大小: :M }, { 大小: :L },{颜色::红色}，{颜色::绿色}，{颜色::黄色}，{价格:1，尺寸::S}，{价格:1，颜色::红色}，{价格:1，颜色::绿色}，{价格:2，尺寸::M}，{价格:2，颜色::绿色}，{ price: 5, size: :M }, { price: 5, size: :L }, { price: 5, color: :yellow },{价格:5，颜色::红色}，{尺寸::S，颜色::红色}，{尺寸::S，颜色::绿色}，{ 尺寸::M，颜色::绿色}，{ 尺寸::M，颜色::黄色}，{ 尺寸::L，颜色::红色 }

{} 表示任何苹果都可以接受.

请注意，客户没有选择粉红色苹果的选项(因为没有)，如果客户为所有三个属性指定了值，则无法做出选择.

对于给定的需求散列，要提供的苹果的选择确定如下:

def 选择(篮子，要求)bag.each_index.select 做 |i|h = 篮子[i]h[:qty] >0 &&要求.全部?{ |属性，值|h[属性] == val }结尾结尾

这将返回 basket 的索引数组，这些索引是 requirements 给定值的允许选择.例如，

choices(basket, { color: :green }) #=>[1, 2]选择(篮子，{价格:1，尺寸::S})#=>[0, 1]选择(篮子，{})#=>[0, 1, 2, 4, 5]

注意数组choices(basket, {})不包括3(粉红苹果，数量为零).

---

我们现在为每个可能的选择计算剩余篮子的多样性度量，并选择导致最大多样性得分的苹果.

defdiversity_of_remaining(篮子，选择)new_basket = bag.each_index.map do |i|我 == 选择?篮子[选择].dup.tap { |h|h[:qty] -= 1 } : 篮子[i]结尾多样性(属性(新篮子))结尾

请参阅Object#tap.

---

假设:

requirements = { color: :red }

然后

arr = 选择(篮子，要求)#=>[0, 5]

然后我们会计算:

apple = arr.max_by { |choice|diversity_of_remaining(篮子，选择)}#=>0

表明 basket[0] 优于 basket[5].请注意:

diversity_of_remaining(basket, 0) #=>9diversity_of_remaining(basket, 5) #=>8

请参阅Enumerable#max_by.

---

以 1.00 美元的价格向客户出售一个小红苹果后，有必要更新 basket 为下一个客户做好准备:

basket[apple][:qty] -= 1

^{1.我对第一个块变量使用了下划线，以向读者表明它未用于块计算.这是常见的做法.}

My code solution currently doesn't cover all possibilities and is half baked... looking for helping completing!

Background

I have an apple basket with any number of attributes, and possible options for those attributes. For example, let's say the 3 attributes I choose to define, as well as the possible options, are:

- price: [1, 2, 5]
- size: [S, M, L]
- color: [Red, Green, Yellow]

In other words, the above says that there are 3 possible prices, 3 possible sizes, 3 possible colors that describe the apples in my basket. However, there's no information on quantity.

For example, this basket could be composed of 3 distinct apples:

- $1, small, red apple
- $2, medium, green apple
- $5, large, yellow apple

Or it could be composed of 12 apples as such:

- 3 $1, small, red apple
- 2 $1, small, green apples
- 2 $2, medium, green apples
- 4 $5, medium, yellow apples
- 1 $5, large, red apple

An important way of thinking about it is, if I were marketing this basket of apples, I want to market it such that the maximum number of options are presented (for the attributes I choose to define), regardless of how many counts of those options exist. In the last example, with the basket of 12 apples, I want to market that I have a large-size and a red-color even though those 2 options occur on a single given apple.

Problem

Given such a marketing strategy, when 1 person orders an apple, I want to give them the apple that meets their requirements while least-constraining the marketability of the rest of my basket. These 2 are kind of the inverse of each other. In my case, I am interested in calculating the greatest number of remaining options after they take their apple (rather than calculating which apple they should take).

3 examples for in the 12 apple basket scenarios above.

1. If someone orders a single $5 apple, I would for sure want to give them a medium yellow apple, rather than a large red apple, because once I give away my large red apple, large-size and red-color are permanently removed from the marketable options I have.

2. However, if someone orders a single $5 red apple, then alas, I have to give away the only large red apple I have, and therefore I lose both large-size and red-color from the list of marketable options

3. If someone orders a single $5 apple (example 1 above) and then a second person orders a large apple, once again I lose both large-size and red-color

Pseudo-code of the method & output:

def remaining_options(order); end

# basket = 12 apple objects as defined in sample scenario above

### EXAMPLE 1
basket.remaining_options([{price:5}])
=> {
  price: [1, 2, 5],
  size: [S, M, L],
  color: [Red, Green, Yellow]
}

basket.remaining_options([{price:5, color: red}])
=> {
  price: [1, 2, 5],
  size: [S, M],
  color: [Green, Yellow]
}

basket.remaining_options([{price:5}, {size: large}])
=> {
  price: [1, 2, 5],
  size: [S, M],
  color: [Green, Yellow]
}

My solution

Just playing around with the examples above, I thought about 2 possible options when someone orders.

1. Their order could be strict enough (e.g., they order using multiple attributes) that only 1 apple is available to them. In this case, all the attributes of that specific apple are deducted from the marketable list.
2. Their order could be loosely defined (e.g., they order on one attribute). In this case, only the ordered attribute is deducted from the marketable list

So here is my solution

# assume there is a model Apple for each apple in the basket where the defined attributes are attributes of the model object itself
# and where apples = basket of 12 apples described above

def remaining_options(order)
  # first, build a count of all basket options for defined attributes; count is independent of each other, since we're maximizing options
  defined_attributes = [:price, :size, :color]
  remaining_options = {}
  defined_attributes.each do |a|
    remaining_options[a] = apples.group(key).count
  end

  # result 
  # remaining_options = {
  #   price: {1=>2, 2=>1, 5=>1},
  #   size: {"S"=>2,"M"=>2,"L"=>1},
  #   color: {"Red"=>2,"Green"=>2,"Yellow"=>1}
  # }

  order.each do |o|
    matched_apples_from_basket = apples.where(o)
    if matched_apples_from_basket.size == 1
      # all attributes of this 1 apple must be subtracted non-independently; it's a capacity constraint
      matched_apple = matched_apples_from_basket.last
      remaining_options.each do |option, count_hash|
        remaining_options[option][matched_apple.send(option)] -= 1
      end
    else
      # loose constraint, we can still deduct independently
      o.each do |option, value|
        remaining_options[option][value] -= 1
      end
    end
  end

  remaining_options.each do |option, count_hash|
    remaining_options[option] = count_hash.reject { |v, count| count < 1 }.keys
  end

  return remaining_options
end

While this solution does work in the test example scenarios that I have mentioned (any errors are bad copy job... hopefully small, sorry), because the query runs on each ordered item independently, this fails when the collection of ordered items itself causes a constraint.

For example, if the order looked like this: [{price:"5"},{price:"5"},{price:"5"},{price:"5"},{price:"5"}], my solution would take each query independently, and independently, $5 isn't a capacity constraint. So my solution would subtract $5 from the option set independently such that at the end, you'd have a remaining set of {price:[1,2],size:["Small","Medium",Large"], color: ["Red", "Green", "Yellow"]}

But this would be wrong, because as a whole, ordering 5 $5 apples means you take all of them, which creates a capacity constraint in the sense that now there will be no more yellow or large apples. So the result should actually be {price:[1,2],size:["Small","Medium"], color: ["Red", "Green"]}

解决方案

Suppose we have an array of hashes of such as the following:

basket = [
  { price: 1, size: :S, color: :red,    qty: 3 },
  { price: 1, size: :S, color: :green,  qty: 2 },
  { price: 2, size: :M, color: :green,  qty: 2 },
  { price: 4, size: :M, color: :pink,   qty: 0 },
  { price: 5, size: :M, color: :yellow, qty: 4 },
  { price: 5, size: :L, color: :red,    qty: 1 },
]

This corresponds to one of the examples given in the question, with one change: I added medium-size pink apples costing $4 for which the quantity on hand is zero. My reason for doing so will become clear.

We may compute the following:

def attributes(basket)
  basket.each_with_object({}) do |g,h|
    g.each do |attr,value|
      h[attr] = Hash.new(0) unless h.key?(attr)
      h[attr][value] += g[:qty] unless attr == :qty    
    end
  end
end

attr = attributes(basket)
  #=> {:price=>{1=>5, 2=>2, 4=>0, 5=>5},
  #    :size=>{:S=>5, :M=>6, :L=>1},
  #    :color=>{:red=>4, :green=>4, :pink=>0, :yellow=>4}}

For example, there are 6 apples with size :M:

basket[2][:qty] + basket[3][:qty] + basket[4][:qty]
  #=> 2 + 0 + 4 = 6

See the form of Hash::new that takes an argument (the default value, here 0) and no block. If h = Hash.new(0) then h[k] returns the default value of zero if h does not have a key k. Initially, for example, h has no keys, so h['cat'] returns 0 (and does not change h). If we set h['cat'] = 9, then of course h['cat'] returns 9 since h now has a key 'cat'.

---

Our measure of diversity for any such hash attributes(basket) could be the following.

def diversity(attributes)
  attributes.sum { |_,g| g.count { |_,cnt| cnt > 0 } }
end

One of the key-value pairs of attributes is

:color=>{:red=>4, :green=>4, :pink=>0, :yellow=>4}}

When this key-value pair is passed to sum's block the block variables are set thusly¹:

_ #=> :color
g #=> {:red=>4, :green=>4, :pink=>0, :yellow=>4}

The block calculation merely counts the number of values of g that are greater than zero.

For this particular basket:

diversity(attr)
  #=> 9

Now suppose an apple is requested with one of the following sets of attributes, which I will refer to as requirements:

{},
{ price: 1 }, { price: 2 }, { price: 5},
{ size: :S }, { size: :M }, { size: :L },
{ color: :red }, { color: :green }, { color: :yellow },
{ price: 1, size: :S }, { price: 1, color: :red }, { price: 1, color: :green }, 
{ price: 2, size: :M }, { price: 2, color: :green },
{ price: 5, size: :M }, { price: 5, size: :L }, { price: 5, color: :yellow },
{ price: 5, color: :red },
{ size: :S, color: :red }, { size: :S, color: :green },
{ size: :M, color: :green }, { size: :M, color: :yellow },
{ size: :L, color: :red }

{} indicates that any apple is acceptable.

Notice that the customer does not have the option of selecting a pink apple (as there are none) and if the customer specifies values for all three attributes there is no choice to be made.

For a given requirements hash the choice of apple to be offered is determined as follows:

def choices(basket, requirements)
  basket.each_index.select do |i|
    h = basket[i]
    h[:qty] > 0 && requirements.all? { |attr, val| h[attr] == val }
  end
end

This returns an array of indices of basket that are permissible choices for the given value of requirements. For example,

choices(basket, { color: :green })      #=> [1, 2]
choices(basket, { price: 1, size: :S }) #=> [0, 1]
choices(basket, {})                     #=> [0, 1, 2, 4, 5]

Note that the array choices(basket, {}) does not include 3 (pink apples, for which the quantity is zero).

---

We now compute the diversity measure of the remaining basket for each possible choice, and select the apple that results in the greatest diversity score.

def diversity_of_remaining(basket, choice)
  new_basket = basket.each_index.map do |i|
    i == choice ? basket[choice].dup.tap { |h| h[:qty] -= 1 } : basket[i]
  end      
  diversity(attributes(new_basket))
end

See Object#tap.

---

Suppose:

requirements = { color: :red }

Then

arr = choices(basket, requirements)
  #=> [0, 5]

We would then compute:

apple = arr.max_by { |choice| diversity_of_remaining(basket, choice) }
  #=> 0

indicating that basket[0] was preferred to basket[5]. Note that:

diversity_of_remaining(basket, 0) #=> 9
diversity_of_remaining(basket, 5) #=> 8

See Enumerable#max_by.

---

After selling the customer a small red apple for $1.00 it would be necessary to update basket in preparation for the next customer:

basket[apple][:qty] -= 1

^{1. I've used an underscore for the first block variable to signal to the reader that it is not used in the block calculation. That is common practice.}

这篇关于优化问题，显示给定一组选择的最大剩余选项数的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！