1

Здравствуйте. Требуется помощь в составлении алгоритма.

  1. Есть общее число необходимой для поставки заказчику продукции.
  2. Есть различные фасовки продукта, которые заказчик может купить. Каждый вид фасовки характеризуется объемом и стоимостью.

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

Пример 1:
Число необходимой продукции: 9л.
Фасовки:
10л - 3852р.
2.5л - 1248р.
1л - 723р.
Наиболее выгодная комбинация: 1*10 (3852р)

Пример 2:
Число необходимой продукции: 6.5 л.
Фасовки:
10л - 3852р.
2.5л - 1248р.
1л - 723р.
Наиболее выгодная комбинация: 3*2.5 = 7.5л (3*1248 = 3744р)

Пример 3:
Число необходимой продукции: 23 л.
Фасовки:
10л - 3852р.
2.5л - 1248р.
1л - 723р.
Наиболее выгодная комбинация: 2*10+1*2.5+1*1 = 23.5л (2*3852 + 1248 + 723 = 9675р)

Насколько я понял, тут у меня модификация задачи о рюкзаке, но не совсем в явном виде.

3
  • 1
    Задача о размене 7 апр 2014 в 21:09
  • Тоже не совсем подходит, т.к.: 1. Вместимость рюкзака (в моём случае число необходимой продукции) может не равняться сумме весов выбранных предметов. Границы не четкие. 2. Мнимизировать нужно не количество взятых предметов, а стоимость полученного варианта. (Хотя, возможно, объем и стоимость имеют прямую зависимость).
    – lightcyber
    7 апр 2014 в 21:24
  • Понятно, что не в точности ваша задача, тем не менее алгоритм можно адаптировать под ваши условия. 1. это ограничение вместимости рюкзака просто добавляет одну итерацию, т.е. проверка не "пока не заполнен", а "пока не переполнен" 2. конечно, чем больше объем тем меньше цена за л, как мне кажется это из условия задачи следует. 7 апр 2014 в 21:36

1 ответ 1

1

Да, это задача о рюкзаке. Единственная особенность - что часть предметов одинакова.

В случае одной фасовки решение находится сразу. Для остальных фасовок надо устраивать перебор. Перебор делается по убыванию размера и количества фасовок, что позволяет оптимизировать алгоритм. Если фасовки идут не в порядке убывания, их следует предварительно отсортировать.

Поскольку количество вложенных циклов заранее неизвестно, следует использовать рекурсию. При выводе переменных применен сдвиг на величину уровня их вложенности, что позволяет различать экземпляры переменных разной вложенности с одинаковым названием. Для хранения и передачи расчётных данных использован массив, содержащий суммарную стоимость и комбинацию фасовок.

Программа на языке PHP:

function print_arr($arr, $text, $m=0){
    print("<br>");
    print(str_repeat("&emsp; ", $m));
    print("$text");
    foreach($arr as $item) print("&emsp;$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

Ваш ответ

By clicking “Отправить ответ”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Всё ещё ищете ответ? Посмотрите другие вопросы с метками или задайте свой вопрос.