mysql — находит минимальное значение в массиве и объединяет все возможные числа для достижения заданной суммы
Не уверен, что следующий сценарий относится к проблеме ранца или подходу к изменению монет. Хотел бы искать решение этой проблемы на языке PHP. Требуется простое решение, потому что не понимают некоторые алгоритмы (теория текста), предоставляемые из Интернета.
Учитывая таблицу (A) следующим образом:
TABLE (A)
---------
Item | Name | Price ($)
-------- ------------ --------------
1 | Adidas | 35
2 | Nike Run | 70
3 | Puma | 100
4 | Nike | 85
5 | NB | 65
- Объедините любой из 3 предметов в таблице (A), суммируйте больше или равный 200 долларам.
- Во-первых, сортировка таблицы (A).
- Во-вторых, получить минимальную / наименьшую сумму (цена). В этом случае 35 долларов.
- В-третьих, проверьте одно за другим количество других.
- В-четвертых, суммируйте 3 варианта комбинации, которые больше или равны 200 долларам.
Результат:
Item | Name | Price ($)
-------- ------------ --------------
1 | Adidas | 35
5 | NB | 65
3 | Puma | 100
Дается еще один образец таблицы (B) следующим образом:
TABLE (B)
---------
Item | Name | Price ($)
-------- ------------ --------------
1 | Adidas | 5
2 | Nike Run | 35
3 | Puma | 110
4 | Nike | 65
5 | NB | 15
- Объедините любой из 3 предметов в таблице (B), суммируйте больше или равный 200 долларам.
- Во-первых, сортировка таблицы (B).
- Во-вторых, получить минимальную / наименьшую сумму (цена). В этом случае 5 долларов.
- В-третьих, проверьте одно за другим количество других.
- В-четвертых, суммируйте 3 варианта комбинации, которые больше или равны 200 долларам.
- В-пятых, если наименьшее объединение с другими и суммой не составило 200 долларов, возьмите второе наименьшее и повторите первый шаг до четвертого шага.
- В-шестых, наилучшее минимальное / наименьшее значение в этом случае составляет 35 долларов.
Результат:
Item | Name | Price ($)
-------- ------------ --------------
2 | Nike Run | 35
4 | Nike | 65
3 | Puma | 110
Решение
Скажем, таблица A является ассоциативным массивом, назовем его $ a.
Чтобы найти первую комбинацию, которая будет> = 200, сделайте это:
$rowsWithValueOver200 = array();
foreach($a as $value) {
foreach($a as $value2) {
// Make sure to ignore the value selected in the first loop.
if ($value2 == $value)
continue;
foreach($a as $value3) {
// Make sure to ignore the value selected in the first and second loop.
if ($value3 == $value)
continue;
if ($value3 == $value2)
continue;
$total = $value3['Price'] + $value2['Price'] + $value['Price'];
if ($total >= 200) {
// Store all of the rows in the new array.
$rowsWithValueOver200[] = $value;
$rowsWithValueOver200[] = $value2;
$rowsWithValueOver200[] = $value3;
break;
}
}
}
}
Таким образом, мы перебираем массив 3 раза. Проверьте сумму, как только мы смотрим на 3 уникальных значения. Все время следите за тем, чтобы мы не включали ранее выбранный элемент массива ($ value или $ value2). Это, конечно, можно немного очистить и сделать более универсальным, но это будет работать для 3 элементов. Рефакторинг этого в более универсальную функцию будет делать рекурсивные вызовы самому себе, учитывать начальную позицию (затем использовать цикл for вместо foreach).
Найти минимальное значение довольно просто.
$minVal = PHP_INT_MAX; // Initially something high, here it is the maximum integer value.
$minRow;
foreach($rowsWithValueOver200 as $value) {
if ($value['Price'] < $minVal){
$minVal = $value['Price'];
$minRow = $value;
}
}
Установите минимальное значение (minVal), чтобы сравнить с чем-то действительно высоким. Выполните итерацию по значениям массива, и если $ value [‘Price’] меньше текущего minVal, то теперь это minVal и сохраните элемент массива в $ minRow для дальнейшего использования.
3 и 4 Я не уверен, что вы спрашиваете. Не ясно.
Если вы хотите найти сумму трех строк в $ rowWithValueOver200, вы можете просто использовать то, что было в первом ответе. Если вы хотите сделать это только с 3 последними элементами, то сделайте это:
$total = 0;
foreach($rowsWithValueOver200 as $value) {
$total += $value['Price'];
}
Если вы ищете другие возможности, в сумме до 200 или более, просто используйте первый пример, но вместо foreach в первом цикле используйте цикл for с индексом. Начните с каждого индекса.
Удачи!
Другие решения
MySQL должным образом оснащен, чтобы выполнить все это самостоятельно. Вы мог потяните всю таблицу за PHP, чтобы понять, но это может дорого обойтись, и это, безусловно, приведет к более медленным результатам, особенно с большими базами данных. PHP обычно должен циклически проходить через данные несколько раз, чтобы выполнить достаточное количество манипуляций с массивами, которые MySQL может выполнить очень легко.
Предполагая, что ваша база данных выглядит так:
CREATE TABLE IF NOT EXISTS `A` (
`Item` int(10) unsigned NOT NULL AUTO_INCREMENT,
`Name` varchar(10) NOT NULL,
`Price` decimal(10,2) NOT NULL,
PRIMARY KEY (`Item`),
UNIQUE KEY `Name` (`Name`)
) ENGINE=InnoDB DEFAULT CHARSET=latin1 AUTO_INCREMENT=6 ;
INSERT INTO `A` (`Item`, `Name`, `Price`) VALUES
(1, 'Adidas', '35.00'),
(2, 'Nike Run', '70.00'),
(3, 'Puma', '100.00'),
(4, 'Nike', '85.00'),
(5, 'NB', '65.00');
Вы можете запросить это так:
SELECT @leastprice := min(`Price`) FROM `A`;
SELECT t1.Name AS Name1, t2.Name AS Name2, t3.Name AS Name3,
t1.Price AS Price1, t2.Price AS Price2, t3.Price AS Price3,
(t1.Price+t2.Price+t3.Price) AS `Total`
FROM `A` t1
LEFT JOIN `A` t2 ON t1.Item != t2.Item
LEFT JOIN `A` t3 ON t1.Item != t2.Item AND t2.Item != t3.Item
WHERE t1.price = @leastprice
AND t2.price<=t3.price
AND t1.price+t2.price+t3.price >= 200;
Результат:
Редактировать:
Для вашего второго случая, если ваша база данных выглядит следующим образом:
CREATE TABLE IF NOT EXISTS `B` (
`Item` int(10) unsigned NOT NULL AUTO_INCREMENT,
`Name` varchar(10) NOT NULL,
`Price` decimal(10,2) NOT NULL,
PRIMARY KEY (`Item`),
UNIQUE KEY `Name` (`Name`)
) ENGINE=InnoDB DEFAULT CHARSET=latin1 AUTO_INCREMENT=6 ;
INSERT INTO `B` (`Item`, `Name`, `Price`) VALUES
(1, 'Adidas', '5.00'),
(2, 'Nike Run', '35.00'),
(3, 'Puma', '110.00'),
(4, 'Nike', '65.00'),
(5, 'NB', '15.00');
Вы можете запросить это так:
SELECT @leastTalliablePrice := min(t1.Price) FROM `B` t1
LEFT JOIN `B` t2 ON t1.Item != t2.Item
LEFT JOIN `B` t3 ON t1.Item != t2.Item AND t2.Item != t3.Item
WHERE t2.price<=t3.price
AND t1.price+t2.price+t3.price >= 200;
SELECT t1.Name AS Name1, t2.Name AS Name2, t3.Name AS Name3,
t1.Price AS Price1, t2.Price AS Price2, t3.Price AS Price3,
(t1.Price+t2.Price+t3.Price) AS `Total`
FROM `B` t1
LEFT JOIN `B` t2 ON t1.Item != t2.Item
LEFT JOIN `B` t3 ON t1.Item != t2.Item AND t2.Item != t3.Item
WHERE t1.price = @leastTalliablePrice
AND t2.price <= t3.price
AND t1.price+t2.price+t3.price >= 200;
Результат:
Если по какой-либо причине в вашей базе данных нет 3 или более отдельных элементов или их цены недостаточно для достижения желаемой суммы, запрос просто вернет 0 строк таким же образом, как если бы SELECT мог получить 0 строк, если это возможно ‘ не найти строки для выбора. Но если бы в приведенном выше случае было более одного совпадения, это привело бы к нескольким строкам, как в случае с моим первым снимком экрана.