Какой алгоритм составить для подбора количества банок?

Question

[reaget]

Здравствуйте!
Исходные данные: объем материала, банки разного объема.
К примеру, нам нужно 33 кг краски. У нас есть одна банка 15 кг и одна банка 7 кг.
Задача подсчитать какое количество и каких банок нам нужно.

Можно взять две по 15 кг и одну 7 кг - 37 кг. Это допустимо, превысить необходимый объем разрешается.
Можно взять пять по 7 кг.

Желательно выбрать первым делом банки максимального объема (в примере это 15 кг), потом банки меньшего и меньшего до тех пор, пока не наберем все банки)

Comments

[Igor Tkhorik]

Если больше 15кг рекурсивно делить на 15 и каждую итерацию записывать в счетчик банька на остаток добавить 1 7кг банку, так тут только так и будет. Очень странная задача. у вас почти всегда будет n*15кг банок + 1 (7кг).

[Роман]

Какой алгоритм составить для подбора количества банок?

Вы уверенны что ваш вопрос именно КАКОЙ алгоритм составить? Точно не КАК составить алгоритм или ПОМОГИТЕ составить алгоритм?

[Сергей Соколов]

смутило слово «одна» в условии:

У нас есть одна банка 15 кг и одна банка 7 кг.

С одной 15 и одной 7 не получить 33..

Answer 1

[reaget]

У меня получилось такое решение. Спасибо большое, что приняли участие и помогли наставлениями :)

var n = 31;
var cans = [10, 15].sort(); // по возрастанию
var res = {};

while (n > 0) {
	let count = -1;
	for (let c in cans) {
		if (cans[c] < n) {
			count++;
		}
		else {
			count++;
			break;
		}
	}

	if (count < 0)
		continue;

	if (!res[ cans[count] ]) res[ cans[count] ] = 0;

	res[ cans[count] ]++;
	n -= cans[count];
}

Answer 2

[Сергей Соколов]

это называется «задача об упаковке» (packing problem) и решается полным перебором всех вариантов.

«Желательно» – это доп. условие, задающее «вес» разным вариантам.
Надо сформулировать функцию потерь: на входе комбинация банок, на выходе «штраф» за неё, который складывается из объёма перебора (недобор не должен вообще приходить), и, может, из количества мелких банок (чтобы минимизировать его).
Перебирая все варианты, считать штрафы, оставлять варианты с минимальными штрафами.

Несколько интересных алгоритмов. См. там ещё ссылки слева.

Comments

[longclaps]

решается полным перебором всех вариантов.

Да ну! O(целевой_объём * количество_номиналов). Тупо минимизируем число банок.

const cans = [15, 7]; // в убывающем порядке
let n = 33;
let dp = Array(n + cans[0]).fill(0);
dp[0] = -1;
for (let can of cans) {
    for (let i = dp.length - can - 1; i >= 0; i--) {
        if (dp[i]) {
            for (let j = i + can; j < dp.length; j += can) {
                if (!dp[j]) dp[j] = can;
            }
        }
    }
}
let res, best = dp.length;
for (let i = dp.length - 1; i >= n; i--) {
    if (dp[i]) {
        let j = i, total = 0, r = [];
        while (j) {
            let can = dp[j], cnt = 0;
            for (; can == dp[j]; j -= can) cnt += 1;
            total += cnt;
            r.push([can, cnt])
        }
        if (best >= total) {
            best = total;
            res = r;
        }
    }
}
console.log(res);

[xmoonlight]

longclaps, эх... да кому тут нужен наш бисер?...
Здесь вообще странно всё в плане логики. Люди сюда приходят не за пониманием, а за исходниками...
Поэтому, ну не нужно пытаться помочь кодом таким, кто не пытается понять логику...

[Сергей Соколов]

longclaps, как и любая задача об оптимизации, эта оптимизируется с учетом условий. Условия не вполне ясны: что хуже, X лишних кг или Y маленьких банок. Поэтому пока только такой ответ.
Согласен, что вероятнее всего минимизируют общее число банок. Но ценой скольких лишних кг это имеет смысл, где порог?

[longclaps]

xmoonlight, я пишу для своего удовольствия. Да ведь и это не ответ, а комментарий, предназначеный тому, кто "в состоянии понять".

[longclaps]

Сергей Соколов, вторую половину кода можно модернизировать, собрав только те решения, каждое из которых будет лучше всех остальных либо по числу банок, либо по перевесу. Можно сообразить, что число таких решений никак не более количества номиналов банок (обычно меньше). Вот плохой пример:

const cans = [3, 1], n = 2;

[ [ 3, 1 ] ] всего банок 1, перевес 1
[ [ 1, 2 ] ] всего банок 2, перевес 0

Мне кажется, делать выбор из такого набора решений полегче )

Answer 3

[xmoonlight]

Задача логарифмической сложности.
Решается через генетический алгоритм с помощью перестановок.
Точка.

Answer 4

[Somewhere Intech]

Пример простой реализации(есть недочёты) на JS, но можно адаптировать на любой в принципе..

function wrap(liquid, cans){
  let result = []
  cans = cans.sort((a,b) => b - a)
  //сортируем все банки по убыванию объёма
  while(cans.length && liquid - cans[0] >= 0){
  //пока есть пустая банка и её объём
  //не превышает объём оставшийся краски
    liquid -= cans[0]
    //вычитаем объём банки
    result.push(cans.splice(0,1)[0])
    //выдираем банку из исходного массива
    //и ложим в результирующий
  }
  while ( liquid > 0 ){
  //пока ещё есть краска
    cans = cans.sort((a,b) => Math.abs(liquid-b) - Math.abs(liquid-a))
    //сортируем по принципу:
    //самой последней должна быть банка,
    //объём которой ближе объёму оставшейся краски
    liquid -= cans[cans.length - 1]
    //вычитаем объём банки
    result.push(cans.pop())
    //выдираем банку из исходного массива
    //и ложим в результирующий
  }
  return result
}

let emptyCans = [15,7,10,12,10]
console.log(wrap(33,emptyCans))
//[15, 12, 7] - эти банки использованы
console.log(emptyCans)
//[10,10] - эти остались