时间戳

首页 > 解决方案 > 优化问题，显示给定选择集合的剩余选项的最大数量

ruby-on-rails - 优化问题，显示给定选择集合的剩余选项的最大数量

问题描述

我的代码解决方案目前并未涵盖所有可能性，并且是半生不熟的......正在寻找帮助完成！

背景

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

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

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

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

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

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

- 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

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

问题

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

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

  1. 如果有人订购一个 5 美元的苹果，我肯定会想给他们一个中等大小的黄色苹果，而不是一个大红苹果，因为一旦我放弃了我的大红苹果，就会large-size永久red-color地从我拥有的适销产品中删除。

  2. 但是，如果有人订购了一个 5 美元的红苹果，那么唉，我不得不放弃我仅有的一个大红苹果，因此我失去了large-size可red-color销售的选项列表

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

方法和输出的伪代码：

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]
}

我的解决方案

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

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

所以这是我的解决方案


# 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

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

例如，如果订单看起来像这样：[{price:"5"},{price:"5"},{price:"5"},{price:"5"},{price:"5"}]，我的解决方案将独立地进行每个查询，并且独立地，$5 不是容量限制。所以我的解决方案会从独立设置的选项中减去 5 美元，这样最后你会得到剩余的一组{price:[1,2],size:["Small","Medium",Large"], color: ["Red", "Green", "Yellow"]}

但这是错误的，因为作为一个整体，订购 5 个 5 美元的苹果意味着你会吃掉所有的苹果，这就造成了容量限制，因为现在不会再有黄色或大苹果了。所以结果实际上应该是{price:[1,2],size:["Small","Medium"], color: ["Red", "Green"]}

标签： ruby-on-railsrubyoptimization

解决方案

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

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 },
]

这对应于问题中给出的示例之一，但有一个变化：我添加了中等大小的粉红苹果，售价 4 美元，手头的数量为零。我这样做的原因将变得很清楚。

我们可以计算以下内容：

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}}

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

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

查看Hash::new的形式，它接受一个参数（默认值，这里0）并且没有块。如果没有键，h = Hash.new(0)则h[k]返回默认值零。例如，最初没有键，因此返回（并且不更改）。如果我们设置，那么当然返回，因为现在有一个键。hkhh['cat']0hh['cat'] = 9h['cat']9h'cat'

我们对任何此类哈希的多样性度量attributes(basket)可能如下。

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

的键值对之一attributes是

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

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

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

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

对于这个特定的篮子：

diversity(attr)
  #=> 9

现在假设使用以下一组属性请求一个苹果，我将其称为需求：

{},
{ 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 }

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

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

对于给定的要求哈希，要提供的苹果的选择如下确定：

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

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

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

请注意，该数组choices(basket, {})不包括3（数量为零的粉红苹果）。

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

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

请参阅Object#tap。

认为：

requirements = { color: :red }

然后

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

然后我们将计算：

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

表示basket[0]首选basket[5]. 注意：

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

请参阅Enumerable#max_by。

在以 1.00 美元的价格向客户出售一个小红苹果后，需要更新basket以准备迎接下一个客户：

basket[apple][:qty] -= 1

1. 我在第一个块变量中使用了下划线来向读者表明它没有用于块计算。这是常见的做法。

推荐阅读