Да, это задача о рюкзаке. Единственная особенность - что часть предметов одинакова.
В случае одной фасовки решение находится сразу. Для остальных фасовок надо устраивать перебор. Перебор делается по убыванию размера и количества фасовок, что позволяет оптимизировать алгоритм. Если фасовки идут не в порядке убывания, их следует предварительно отсортировать.
Поскольку количество вложенных циклов заранее неизвестно, следует использовать рекурсию. При выводе переменных применен сдвиг на величину уровня их вложенности, что позволяет различать экземпляры переменных разной вложенности с одинаковым названием. Для хранения и передачи расчётных данных использован массив, содержащий суммарную стоимость и комбинацию фасовок.
Программа на языке PHP:
function print_arr($arr, $text, $m=0){
print("<br>");
print(str_repeat("  ", $m));
print("$text");
foreach($arr as $item) print(" $item");
}
function opt_cost($cond, $volume, $var=[], $m=0){
// Начальный вариант - заполнение текущей фасовкой
$n_max = ceil($volume / $cond[$m][0]);
$var_opt = $var;
$var_opt[0] += $cond[$m][1] * $n_max;
$var_opt[$m+1] = $n_max;
print_arr($var_opt, "var_opt =", $m);
// Если фасовка не последняя, то проверяем все варианты
if($m != count($cond)-1){
for($n = $n_max-1; $n >=0; $n--){
$var_new = $var;
$var_new[0] += $cond[$m][1] * $n;
$var_new[$m+1] = $n;
$volume_new = $volume - $n*$cond[$m][0];
$var_new = opt_cost($cond, $volume_new, $var_new, $m+1);
if($var_new[0] < $var_opt[0]){
$var_opt = $var_new;
print_arr($var_opt, "var_opt = ", $m);
}
}
}
// Оптимальная фасовка при заданных параметрах
return $var_opt;
}
function opt_proc($volume, $cond){
print("Потребность: $volume");
foreach($cond as $key => $item){
print_arr($item, "Вариант $key (фасовка, цена): ");
}
print("<br>");
$cost = opt_cost($cond, $volume);
print_arr($cost,"Минимальная цена: ");
print("<br><br>");
}
$cond = [[10.0, 3852], [2.5, 1248], [1.0,723]];
opt_proc(9, $cond);
opt_proc(6.5, $cond);
opt_proc(23, $cond);
Результаты:
Потребность: 9
Вариант 0 (фасовка, цена): 10 3852
Вариант 1 (фасовка, цена): 2.5 1248
Вариант 2 (фасовка, цена): 1 723
var_opt = 3852 1
var_opt = 4992 0 4
var_opt = 5190 0 3 2
var_opt = 5388 0 2 4
var_opt = 6309 0 1 7
var_opt = 6507 0 0 9
Минимальная цена: 3852 1
Потребность: 6.5
Вариант 0 (фасовка, цена): 10 3852
Вариант 1 (фасовка, цена): 2.5 1248
Вариант 2 (фасовка, цена): 1 723
var_opt = 3852 1
var_opt = 3744 0 3
var_opt = 3942 0 2 2
var_opt = 4140 0 1 4
var_opt = 5061 0 0 7
var_opt = 3744 0 3
Минимальная цена: 3744 0 3
Потребность: 23
Вариант 0 (фасовка, цена): 10 3852
Вариант 1 (фасовка, цена): 2.5 1248
Вариант 2 (фасовка, цена): 1 723
var_opt = 11556 3
var_opt = 10200 2 2
var_opt = 9675 2 1 1
var_opt = 9675 2 1 1
var_opt = 9873 2 0 3
var_opt = 9675 2 1 1
var_opt = 11340 1 6
var_opt = 10815 1 5 1
var_opt = 10815 1 5 1
var_opt = 11013 1 4 3
var_opt = 11934 1 3 6
var_opt = 12132 1 2 8
var_opt = 13053 1 1 11
var_opt = 13251 1 0 13
var_opt = 12480 0 10
var_opt = 11955 0 9 1
var_opt = 11955 0 9 1
var_opt = 12153 0 8 3
var_opt = 13074 0 7 6
var_opt = 13272 0 6 8
var_opt = 14193 0 5 11
var_opt = 14391 0 4 13
var_opt = 15312 0 3 16
var_opt = 15510 0 2 18
var_opt = 16431 0 1 21
var_opt = 16629 0 0 23
Минимальная цена: 9675 2 1 1