0

我们的网站计算出订单的总运费，我们数据库中的每件商品都有一个立方尺寸，并且对于使用快递和运费的商品有大小限制。但是我们收到了多件商品的订单，我注意到它在不需要时将其称为运费。

每张快递票的包裹限制为0.15m3，如果超过，他们必须通过货运代替。顺便说一句，小件托运的运费更高，因为有最低费用，如果没有，这根本不是问题。

我在这里问是因为我们的程序员在离开这个国家之前的时间有限，这不是我们给他的紧急任务之一，如果我们要完成它，那么我需要帮助他朝着正确的方向前进 -但唉，我不是程序员。

问题：
一个订单有 2 件商品，每件都是 0.106 到本地地址

  • 网站称它为 0.212，运费为 $42
  • 我们可以用快递运送 2 盒，总共 10 美元

但仅在任何一件商品大于 0.15 的限制时才需要使用运费，
因此，它将将该订单视为 (0.106=$5) 和 (0.106=$5) = $10

例如：

  1. 假设有更复杂的东西：
    购物车中有 10 件商品，每件 0.02 件。网站会将其计算为 0.2 并称其为运费，但我们可以将其放在 2 个盒子中并支付 10 美元

  2. 购物车中有 5 件商品，0.01 x 4 和 0.12 x 1。网站会将其计算为 0.16 并称之为运费，但我们可以发送 2 个纸箱 - 0.04 和 0.12，成本为 10 美元

它可以这样做吗：如果任何一件物品大于 0.15，则全部为运费，否则加起来需要多少张票，假设我们尽可能装进最大的盒子示例 2： 

(0.01+0.01+0.01+0.01)=0.04=$5,
(0.12)=0.12=$5 
==$10

我知道这很棘手，但这只是数学，而且最重要，因为荒谬的运费可能会停止订单。

4

2 回答 2

2

就像@AlistairIsrael 说的那样，这是装箱问题，解决起来并不容易。

但是，以下是解决此问题的一种方法。

如果我们通过所有方式组合来包装物品并尝试找到最低成本，那么我们就有了解决方案。请注意，此解决方案是一种蛮力解决方案，因此会随着项目数量的增长而迅速放缓。

寻找所有可能的方式将货物分成不同的箱子；我们可以使用这个答案中的算法：

用于查找从 Python 到 Ruby 的集合的所有分区的翻译函数

接下来，我们遍历所有不同的组合并搜索最小成本。然后解决方案的工作方式如下：

> optimize_shipping([0.01, 0.01, 0.01, 0.01, 0.12])
Shipping type: courier
Total price  : $10
Packaging    : [[0.12], [0.01, 0.01, 0.01, 0.01]]

> optimize_shipping([0.01, 0.01, 0.12, 0.15, 0.12])
Shipping type: courier
Total price  : $15
Packaging    : [[0.01, 0.12], [0.15], [0.01, 0.12]]

> optimize_shipping([0.09, 0.09, 0.01, 0.12, 0.15, 0.12])
Shipping type: courier
Total price  : $25
Packaging    : [[0.12], [0.15], [0.12], [0.09, 0.01], [0.09]]

> optimize_shipping([0.01, 0.01, 0.01, 0.30])
Shipping type: freight

编码：

COURIER_LIMIT = 0.15
COURIER_PRICE = 5

class Array
  def sum
    inject(:+)
  end

  def partitions
    yield [] if self.empty?
    (0 ... 2 ** self.size / 2).each do |i|
      parts = [[], []]
      self.each do |item|
        parts[i & 1] << item
        i >>= 1
      end
      parts[1].partitions do |b|
        result = [parts[0]] + b
        result = result.reject do |e|
          e.empty?
        end
        yield result
      end
    end
  end
end

def optimize_shipping(boxes)
  if boxes.any? { |b| b > COURIER_LIMIT }
    puts "Shipping type: freight"
    return
  end

  # Try and find the cheapest most optimal combination of packaging
  smallest_box   = 9999
  cheapest_price = 9999
  cheapest_combination = []

  # Go through all paritions and find the optimal distribution
  boxes.partitions { |partition|
    # Add up sizes per box
    sizes = partition.map(&:sum)

    # Check if any box got too big for courier, and skip if so
    next if sizes.any? { |s| s > COURIER_LIMIT }

    # Calculate total price for this combination
    total_price = partition.length * COURIER_PRICE

    if total_price <= cheapest_price
      # Naive algo to try and find best average distriution of items
      next if total_price == cheapest_price && sizes.min < smallest_box

      # Save this new optimized shipment
      smallest_box         = sizes.min
      cheapest_price       = total_price
      cheapest_combination = partition
    end
  }

  puts "Shipping type: courier"
  puts "Total price  : $#{cheapest_price}"
  puts "Packaging    : #{cheapest_combination.inspect}"
end
于 2013-06-21T04:55:32.180 回答
0

没有显示代码，但基本上，您会接受可能是数组之类的集合的订单，然后执行以下操作：

orders = [0.01,0.16,0.01,0.01]
freight = orders.any? {|item| item > 0.15 }

当然，需要更多的逻辑，但您现在可以将运费作为 true 或 false 作为布尔值来继续进行所需的工作。

相信count在这里也能成为你的朋友。

于 2013-06-21T03:56:13.823 回答