Как узнать какие товары входят в ценник, если известна итоговая сумма?

Question

[Радость моя]

Привет друзья. Всю ночь ковырял код, пытался понять как так сделать. Есть сумма заказа и есть товары. Надо вычислить какие товары спрятаны в этой сумме. Думал про рекурсию и остаток отделения, но в код это собрать не могу. Настоящая головоломка для моей логики :)

Мой код на php:

<?php

// Входящие данные
$article = 'hp'; // артикул товара
$sum = 3563; //Сумма (для теста тут принтер hp + 4 катриджа: hpb*3 + hpr*1)

// принтеры
$printersPrice = [
	'canon' => 1000,
	'hp' => 2000,
	'xerox' => 3000,
];

// катриджи
$accessories = [
	'canon' => [
		'cnb' => 390,
		'cnbxl' => 490,
	],
	'hp' => [
		'hpr' => 390,
		'hpb' => 391,
		'hpg' => 392,
		'hpk' => 393,
	],
];

$accessoriesSum = $sum - $printersPrice[$article]; // вычитаем стоймость принтера из общей суммы
$basket = [];

buildBasket(...) {...}

/*

на выходе ожидается массив такого содержания
[
	hpb => 3,
	hpr => 1,
]

или false если цена специально неправильно составлена

**/

Comments

[Влад Невлад]

уточните: с одним принтером может идти только один картридж или нет? :)

[Радость моя]

нет, может быть несколько разных (3 одинаковых + 1 разный например). но только 1 принтер в заказе. и катриджи только к этому принтеру.

[Илья Герасимов]

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

[Радость моя]

если цена одинаковая- брать любой катридж просто. это сферическая задача, в тестовом задании.

[Илья Герасимов]

t-alexashka, чем больше товаров нам нужно будет подобрать (и сколько у нас их всего), тем больше у нас будет возможных комбинаций, перебирай их пока не совпадет итоговая сумма, слишком трудоемкая задача для тестового задания или я не вник ._.

[Stalker_RED]

t-alexashka, или вы неправильно поняли задание или вам его дали какие-то сумасшедшие (тогда бегите от них).

[Радость моя]

Илья Герасимов, Илья, все товары что возможны указанны в массивах. и их аксессуары. повторю - задача про сферического коня, этот код не боевой, а просто на логику. Я думал использовать остаток от деления $a % $b в рекурсии вытягивая оставшиеся элементы из массива и собирая из этого корзину. но в голове одно а в код перевести совсем другое :) принтер в заказе может быть только 1. те данные что сверху написаны - по легенде они пришли по API, и надо угадать какие катриджи купили помимо принтера (стоимость принтера на примере выше вычитается из суммы, и остается как раз сумма всех купленных аксессуаров). к принтеру может быть только катриджи для него. т.е. если принтер hp то и катриджи только те что в секции hp в массиве аксессуаров.

[Радость моя]

Stalker_RED, задача понята правильно, а бежать некуда. семью кормить надо :)

[Stalker_RED]

t-alexashka, похоже на разновидность задачи о ранце, она почти во всех учебниках по алгоритмам есть.

[Lynn «Кофеман»]

А что делать если ответов несколько? У вас в примере подходят 3hpr+hpk и 3hpb+hpr

[Сергей delphinpro]

t-alexashka,

задача про сферического коня, этот код не боевой, а просто на логику.

По логике задача не имеет однозначного решения. При одних и тех же входных данных имеется от 0 до n результатов.

Поэтому вас правильно спрашивают — какие еще условия есть?

Answer 1

[Rsa97]

Простейшая рекурсия.

function makeBasket($sum, $prices, $result) {
    if ($sum % $prices[0] == 0) {
        return array_merge($result, [$sum / $prices[0]]);
    }
    if (count($prices) == 1) {
        return false;
    }
    for ($i = 0; $i <= $sum / $prices[0]; $i++) {
        $res = makeBasket($sum - $prices[0] * $i, array_slice($prices, 1), array_merge($result, [$i]));
        if ($res != false) {
            return $res;
        }
    }
    return false;
}

$prices = array_values($accessories[$article]);
$res = makeBasket($accessoriesSum, $prices, []);
$result = [];
$i = 0;
foreach ($accessories[$article] as $key => $val) {
    if (($i < count($res)) && ($res[$i] != 0)) {
        $result[$key] = $res[$i];
    }
    $i++;
}
print_r($result);

Возвращает первый найденный результат.
sandbox.onlinephpfunctions.com/code/f9d233c85ed30b...

Comments

[Радость моя]

Rsa, спасибо, это то что нужно. 100 лет тебе удачи.

[Радость моя]

рано я обрадовался :(
если взять сумму 2760: принтер canon (1000) да по 2 его катриджа (cnb*2 + cnbxl*2) то возвращает пустой массив.

[Rsa97]

t-alexashka, А вы $article не забыли изменить?
sandbox.onlinephpfunctions.com/code/4f2d214b363290...

[Радость моя]

Rsa97, да, прошу прощения :)