Как посчитать количество поддонов оптимально?

Question

[Алексей Ярков]

Всем привет. Другу для своего минизавода нужна программка.

Тех задание: имеется 3 вида поддонов: 72 блока, 84 блока и 90 блоков, задача смонтировать диалог в который забивается кол-во блоков, а программа рассчитывает оптимальное соотношение поддонов под максимально близкое к этому количеству.

Например: есть 1043 блока. Вводим количество, и программа выдает - нужно 5 таких и 7 таких поддонов. В общем на 13 поддонов влезет 1050 блоков (чуть больше задуманного). Но не меньше.

Прошу подсказать алгоритм решения. Можно на JS или Python.

Всем спасибо.

Comments

[Aves]

rosettacode.org/wiki/Knapsack_problem/Unbounded

Answer 1

[Aves]

Проще всего банально перебором

var p72 = {count: 72};
var p84 = {count: 84};
var p90 = {count: 90};

var items = [p72, p84, p90];
var count = 1043;
var minVal = Infinity;
var solutions = [];
var val;

for (var i = 0, item = items[i]; i < items.length; item = items[++i]) item.max = Math.ceil(count / item.count);

for (p72.i = 0; p72.i <= p72.max; p72.i += 1)
  for (p84.i = 0; p84.i <= p84.max; p84.i += 1)
    for (p90.i = 0; p90.i <= p90.max; p90.i += 1) {
      val = p90.i * p90.count + p84.i * p84.count + p72.i * p72.count;
      if (val < count) continue;
      if (val < minVal) {
        solutions = [];
        solutions.count = val;
        minVal = val;
      }
      if (val === minVal) solutions.push([p72.i, p84.i, p90.i]);
    }

console.log(solutions); // 1044 9 вариатнов

Answer 2

[Никита]

У меня по математике было 3, но всё же попробую. Берите количество блоков и делите на самый большой поддон без остатка. 1043/90 = 11.
Остаток пытаемся засунуть в более мелкие поддоны 1043-990=53/72 ->1.
Итого: 11 по 90 и 1 по 72.
Но это алгоритм без весов (стоимости поддонов). С удовольствием послушаю математиков.

Answer 3

[Saboteur]

IMHO в вашем случае проще решить простым перебором всех вариантов.

#!/usr/bin/env python

rack_s=0 #72
rack_m=0 #84
rack_b=0 #90
min_b=0
min_m=0
min_s=0
empty=1000

for blocks in range(70,100):
  empty=blocks

  for rack_b in range(0,100):
    for rack_m in range(0,100):
      for rack_s in range (0,100):
        space=rack_s * 72 + rack_m * 84 + rack_b * 90
        if space >= blocks:
          if empty > (space - blocks):
            empty=space - blocks
            min_b=rack_b
            min_m=rack_m
            min_s=rack_s
          break
  print ("Blocks:", blocks, "	Empty blocks :",empty, "	Racks: Big, Medium, Small:", min_b, min_m, min_s)

Табличку сохранить и пользоваться готовым.

Answer 4

[Igor Makarov]

Knapsack_problem

Comments

[Saboteur]

IMHO похоже, но чуток другое, копипаст в лоб не подойдет. Там нужно как можно больше впихнуть, а тут впихнуть определенное кол-во в разного размера рюкзаки.