Смятане на варианти - оптимизация на бройките ползван материал.

[uphero]

Нещо зациклих на уж проста задача:
Имаме тръби по 6000мм от които трябва да отрежем примерно следните парчета
1. 20 х 5000мм
2. 4 х 1000мм
3. 1 х 100мм


Трябва да се извъртят всички възможни комбинации и да извадим колко най-малко тръби са нужни и от всяка една тръба която се реже колко мм остават.

1 тръба -> остава 200 мм
- 2 х парче ХХХ мм
- 1 х парче ХХХ мм

2 тръба -> остава 550 мм
- 4 х парче ХХХ мм
- 2 х парче ХХХ мм

 

[anonimen]

Винаги ли поначало са дадени тръби с еднакъв размер? Тогава долното разграничение не се случва.

В противен случай обаче, има разлика дали броя тръби искаш да оптимизираш, или количеството изхвърлени изрезки.
Ако имаш тръби по 6м и по 1м, и трябва да отрежеш две парчета по 1м, то:

• в първия случай е по-ефективно да отрежеш 2 парчета по един метър от една 6-метрова тръба – при което ще оотанат 4 метра излизшък,
• а във втория ще е по-ефективно да вземеш две тръби от еднометровите – и тогава ще останат 0 метра излишък.

 

[uphero]

Тръбите са само един размер - 6 метра в примера.
Задачата е да сметнем колко минимум тръби ни трябват за дадените парчета които трябва да се изрежат от тях.

При рязане ако ни останат както си казал парче 1метър и ни трябват още 2 по 1 м. то ще вземем оставащото и ще отрежем още една тръба или пишем + 1 в общия брой (всяка започната ни трябва, дори и 1мм да се реже от нея)

 

[anonimen]

Окейй, на първо четене най-просто е да пробваш с алчния алгоритъм.

Два списъка, един със supplyя и един с demand'а. И в двата записваш двойки (брой, дължина), и ги държиш сортирани по дължината - supply ascending, demand descending.
На всяка итерация гледаш най-дългата тръба от demandа, взимаш най-късата тръба от supply'я, която я побира, и режеш от нея.

Работи върху твоя пример, ето ги стъпките (разделих всичко на 100, да не пиша нули), като отдясно на чертата съм разписал останките
(20x10 значи "20 oстанки по 10дм", 1х9+15х10 значи "от 1 тръба остават 9дм, от 15 тръби остават 10дм")

И на всяка стъпка държа списъците сортирани, supply нагоре, demand надолу.

Обаче намерих контрапример - не работи във всички случаи (ако дадените тръби са с дължина 10м, и ти трябват тръби (6,5,3,2,2,2), на тоя алгоритъм му трябват 3 тръби, а то може само с 2). Та трябва да се поправи някак.

 

[anonimen]

Най-грубият начин да го поправиш е на всяка стъпка да изпробваш един по един всички варианти за изрязване (като рекурсивно след всеки опит продължаваш докрай), и да връщаш най-оптималния. Тоест, ако вземеш моя контрапример и стигнеш до стъпка, в която

supply=(1x4, 1x5, infinity x 10)
demand=(1x3, 3x2)

(тая стъпка се стига като сложиш 6тицата и петицата - тях няма откъде да ги вземеш освен от две 10метрови тръби)

тo в тоя случай взимаш една тройка от demand и изпробваш рекурсивно всички варианти да я вземеш от supply'я:
1. Ако отрежеш от 4-метровата тръба - и пускаш алгоритъма надолу в тоя случай и взимаш резултата накрая.
2. Ако отрежеш от 5-метровата тръба - пак пускаш надолу рекурсивно и взимаш резултата
3. Ако отрежеш от нова 10-метрова тръба - пак рекурсивно
И накрая връщаш оптималния резултат.

Като тая рекурсия я правиш навсякъде, и става експоненциално бавно. Но пък ако времето не ти е проблем (а и пространството май), така ще работи коректно винаги.

 

[Revelation]

Обаче намерих контрапример - не работи във всички случаи (ако дадените тръби са с дължина 10м, и ти трябват тръби (6,5,3,2,2,2), на тоя алгоритъм му трябват 3 тръби, а то може само с 2). Та трябва да се поправи някак

Може и да се получи, ако се взима предвид четни и нечетни числа. Ако имаш нечетно число деманд, вероятно е по-добре да намериш най-късата нечетна тръба, за да останеш с четно число.
Тогава може и да се покрият такива недостатъци.
Но тука говорим и за доста кръгли числа. Ако не са кръгли нещата може и да станат грозни.

 

[anonimen]

Може и да се получи, ако се взима предвид четни и нечетни числа. Ако имаш нечетно число деманд, вероятно е по-добре да намериш най-късата нечетна тръба, за да останеш с четно число.

Хмм, тогава вземи контрапримера и умножи всичко в него по 2. Тогава всички supply и demand числа ще са винаги четни и модификацията с нечетностите няма да промени прилагането на алгоритъма, т.е. той ще даде същия (грешен) резултат.

 

[uphero]

Май съм подценил задачата Доста по сложно било

 

[Revelation]

Преди бях писал подобен алгоритъм. Там не беше с тръби, а хотелски стаи. Определен брой стаи с двойни легла, единични, две единични и при определен вход трябваше да разпределя групи хора по най-добрия начин.
Не знам дали го имам някъде запазен все още.

Ако се изисква наистина прецизност, то тогава може да се наложи да се групират деманд тръби предварително в размери, които се събират в една тръба.

В примера при размер 10м тръба.
6,5,3,2,2,2 могат примерно да се групират така: 6,2,2 и 5,3,2

Това е, ако знаем предварително входа. Но, ако деманда е динамичен и не знаем предварително размерите, то тогава някои ще трябват да се лепят на опашка докато се състави група. Ако деманда свърши и имаме непълна група, изпълняваме я с нова тръба.

Трябва да се разпише, защото е лесно да не се обмислят варианти, които да не сработят.

 

[anonimen]

В примера при размер 10м тръба.
6,5,3,2,2,2 могат примерно да се групират така: 6,2,2 и 5,3,2

Това е, ако знаем предварително входа.

То ако входът е даден, вече в задачата се търси не алгоритъм, ами по-скоро доказателство, че намереният оптимум наистина е оптимален
Иначе това с групирането 622,532 е и резултата при "поправения" алчен алгоритъм, доколкото го проследих.

Май съм подценил задачата Доста по сложно било

Не е толкова сложно, просто е рекурсия с цикъл, ето малко по-формално описание на semi-python pseudocode на алгоритъма от по-горния ми пост:

def alg(demand, supply):
    if demand.empty():
        return proper zero state - 0 тръби
 
    (wanted_count, wanted_len) = demand.pop()

    options = {}
    for i, (supply_count, supply_len) in supply.enumerate():
        if supply_len >= wanted_len:
            new_demand = demand + (wanted_count - 1, wanted_len)
            new_supply = supply with i replaced by (supply_count - 1, supply_len) or removed if supply_count = 1
            options[i] = alg(new_demand, new_supply) # рекурсията
 
    return options.min by pipes used # при бройката на тръбите тук отчиташ дали си взел нова тръба (от тия с infinity за supply_len) или изрезка от стара

Ще трябва да попълниш, разбира се, pseudocode частите с истинските данни, които искаш да върнеш (там кои тръби как си попълнил и колко им е останало), но общо взето е това - brute-force решението, де. Друго на момента не ми хрумва на първо четене. Но може да тестваш с това, дали върви достатъчно бързо, и едва после да търсиш оптимизации.
Може да почнеш само с бройката на тръбите и да тестваш върху двата примера досега.

 

[Revelation]

Под знаем предварително входа имах предвид, че пускаш програмата да речем със 100 размера наведнъж. Не е задължително да знаеш размерите, защото може да са генерирани, но програмата взима входа при стартиране и приключва.

При динамичен вход визирах някакъв тип стрийм докато програмата върви. Пускаш да речем по 3 или 4 размера на един път, което би имитирало поръчки и програмата изчислява, когато решиш да я спреш или на определен интервал.

 

[uphero]

То ако входът е даден, вече в задачата се търси не алгоритъм, ами по-скоро доказателство, че намереният оптимум наистина е оптимален
Иначе това с групирането 622,532 е и резултата при "поправения" алчен алгоритъм, доколкото го проследих.


Не е толкова сложно, просто е рекурсия с цикъл, ето малко по-формално описание на semi-python pseudocode на алгоритъма от по-горния ми пост:

def alg(demand, supply):
    if demand.empty():
        return proper zero state - 0 тръби
 
    (wanted_count, wanted_len) = demand.pop()

    options = {}
    for i, (supply_count, supply_len) in supply.enumerate():
        if supply_len >= wanted_len:
            new_demand = demand + (wanted_count - 1, wanted_len)
            new_supply = supply with i replaced by (supply_count - 1, supply_len) or removed if supply_count = 1
            options[i] = alg(new_demand, new_supply) # рекурсията
 
    return options.min by pipes used # при бройката на тръбите тук отчиташ дали си взел нова тръба (от тия с infinity за supply_len) или изрезка от стара

Ще трябва да попълниш, разбира се, pseudocode частите с истинските данни, които искаш да върнеш (там кои тръби как си попълнил и колко им е останало), но общо взето е това - brute-force решението, де. Друго на момента не ми хрумва на първо четене. Но може да тестваш с това, дали върви достатъчно бързо, и едва после да търсиш оптимизации.
Може да почнеш само с бройката на тръбите и да тестваш върху двата примера досега.

Не се ориентирам в кода обаче?
Какво трябва да подам на функцията?

 

[anonimen]

Два списъка, един със supplyя и един с demand'а. И в двата записваш двойки (брой, дължина), и ги държиш сортирани по дължината - supply ascending, demand descending.
Копирах си дословно изречението от по-горния пост
В твоя пример това са [(infinity, 6000)] и [(20, 5000), (4,1000), (1, 100)].

 

[deam0n]

Може и да се получи, ако се взима предвид четни и нечетни числа. Ако имаш нечетно число деманд, вероятно е по-добре да намериш най-късата нечетна тръба, за да останеш с четно число.
Тогава може и да се покрият такива недостатъци.
Но тука говорим и за доста кръгли числа. Ако не са кръгли нещата може и да станат грозни.

Реално ще му трябват 3 ако искаме да сме pixel perfect

 

[anonimen]

Реално ще му трябват 3 ако искаме да сме pixel perfect

Щото при рязането ще изпили по 1мм на всеки разрез ли

 

[deam0n]

Щото при рязането ще изпили по 1мм на всеки разрез ли

Да

 

[uphero]

Да

5мм са, ама тях ще ги сложа в дължината на парчето и реално няма отношение тук.

 

[Revelation]

Значи имаш и margin В такъв случай наивен алгоритъм може би ти стига хаха.

 

[uphero]

Пробвах с чатбота ама нещо не му работи кода, 100 пъти го фиксва и все 0 му е резултата

<?php

function findMinPipes($tubeLength, $pieces) {
    $minPipes = PHP_INT_MAX;

    foreach (getCombinations($pieces) as $combination) {
        $usedPipes = [];
        $isValidCombination = true;

        foreach ($combination as $pieceLength) {
            $sortedTubeLengths = array_reverse(array_values(array_unique($pieceLength)));

            foreach ($sortedTubeLengths as $length) {
                if ($tubeLength >= $length && !in_array($length, $usedPipes)) {
                    $usedPipes[] = $length;
                    break;
                } else {
                    $isValidCombination = false;
                    break;
                }
            }
        }

        if ($isValidCombination) {
            $minPipes = min($minPipes, count($usedPipes));
        }
    }

    return ($minPipes === PHP_INT_MAX) ? 0 : $minPipes;
}

function getCombinations($arrays) {
    $result = [[]];

    foreach ($arrays as $arr) {
        $newResult = [];

        foreach ($result as $item) {
            foreach ($arr as $val) {
                $newResult[] = array_merge($item, [$val]);
            }
        }

        $result = $newResult;
    }

    return $result;
}

$tubeLength = 6000;
$pieces = [
    array_fill(0, 20, 5000),
    array_fill(0, 4, 1000),
    array_fill(0, 1, 100)
];

$result = findMinPipes($tubeLength, $pieces);
echo "Минимален брой тръби: $result\n";

?>

 

[uphero]

<?php

// Function to calculate the number of pipes needed for a given combination
function calculatePipesNeeded($combination, $pipeLength)
{
    $totalLength = 0;

    foreach ($combination as $piece) {
        $totalLength += $piece['length'] * $piece['count'];
    }

    return ceil($totalLength / $pipeLength);
}

// Given pipe length
$pipeLength = 6000;

// Required pieces and their lengths and counts
$pieces = [
    ['length' => 5000, 'count' => 20],
    ['length' => 1000, 'count' => 4],
    ['length' => 100, 'count' => 1],
];

// Initialize variables to store the minimum number of pipes needed and the corresponding combination
$minPipesNeeded = PHP_INT_MAX;
$minCombination = [];

// Function to generate combinations iteratively
function generateCombinations($pieces, $pipeLength)
{
    $minPipesNeeded = PHP_INT_MAX;
    $minCombination = [];

    $count = count($pieces);

    for ($i = 0; $i < (1 << $count); $i++) {
        $currentCombination = [];

        for ($j = 0; $j < $count; $j++) {
            $piece = $pieces[$j];
            $currentCombination[] = [
                'length' => $piece['length'],
                'count' => ($i & (1 << $j)) ? $piece['count'] : 0,
            ];
        }

        $pipesNeeded = calculatePipesNeeded($currentCombination, $pipeLength);

        if ($pipesNeeded < $minPipesNeeded) {
            $minPipesNeeded = $pipesNeeded;
            $minCombination = $currentCombination;
        }
    }

    return $minCombination;
}

// Generate combinations
$result = generateCombinations($pieces, $pipeLength);

// Output the result
echo "Minimum number of pipes needed: " . calculatePipesNeeded($result, $pipeLength) . "\n";
echo "Optimal combination:\n";
foreach ($result as $piece) {
    if ($piece['count'] > 0) {
        echo "{$piece['count']} pieces of {$piece['length']}mm\n";
    }
}

<?php

// Function to calculate the number of pipes needed for a given combination
function calculatePipesNeeded($combination, $pipeLength)
{
    $totalLength = 0;

    foreach ($combination as $piece) {
        $totalLength += $piece['length'] * $piece['count'];
    }

    return ceil($totalLength / $pipeLength);
}

// Given pipe length
$pipeLength = 6000;

// Required pieces and their lengths and counts
$pieces = [
    ['length' => 5000, 'count' => 20],
    ['length' => 1000, 'count' => 4],
    ['length' => 100, 'count' => 1],
];

// Initialize variables to store the minimum number of pipes needed and the corresponding combination
$minPipesNeeded = PHP_INT_MAX;
$minCombination = [];

// Function to generate combinations iteratively
function generateCombinations($pieces, $pipeLength)
{
    $minPipesNeeded = PHP_INT_MAX;
    $minCombination = [];

    $count = count($pieces);

    for ($i = 0; $i < (1 << $count); $i++) {
        $currentCombination = [];

        for ($j = 0; $j < $count; $j++) {
            $piece = $pieces[$j];
            $currentCombination[] = [
                'length' => $piece['length'],
                'count' => ($i & (1 << $j)) ? $piece['count'] : 0,
            ];
        }

        $pipesNeeded = calculatePipesNeeded($currentCombination, $pipeLength);

        if ($pipesNeeded < $minPipesNeeded) {
            $minPipesNeeded = $pipesNeeded;
            $minCombination = $currentCombination;
        }
    }

    return $minCombination;
}

// Generate combinations
$result = generateCombinations($pieces, $pipeLength);

// Output the result
echo "Minimum number of pipes needed: " . calculatePipesNeeded($result, $pipeLength) . "\n";
echo "Optimal combination:\n";
foreach ($result as $piece) {
    if ($piece['count'] > 0) {
        echo "{$piece['count']} pieces of {$piece['length']}mm\n";
    }
}