Другие языки программирования и технологии

Дано от 3х до N количества бутылок, каждая имеет свое содержание спирта и сахара, необходимо вычислить сколько и из како

Джони Депп
Джони Депп
385
Самый простой способ, как уже писал Алексей - рекурсивный перебор. Правда, чем больше N, тем дольше придется ждать ;)
Так как нет условия подобрать самый оптимальный вариант, можно комбинировать перебор с ru.wikipedia.org/wiki/Жадный_алгоритм.
А еще есть динамеческое программирование ru.wikipedia.org/wiki/Динамическое_программирование и ru.wikipedia.org/wiki/Программирование_в_ограничениях (библиотеки есть и для плюсов, жабы, питона и прочего зоопарка ;) )

Принцип довольно простой: вы указываете все возможные ограничения и предоставляете выбор конкретного алгоритма решения библиотеке.
Конечно, неплохо бы иметь хотя бы грубое представление о том, как это все работает - но по-любому, в большинстве случаев, будет в сто раз быстрее собственных велосипедов ;)

Главное - правильно сформулировать задачу:
предположим, у нас 3 бутылки b1,b2,b3
b1(100 у.е. спирта, 100 у.е сахара)
b2(300, 10)
b3(100, 20)
нужен коктейль с(100,50)
т.е для решения достаточно знать, какую часть содержимого b1, b2, b3 лить в коктейль.
т.е ищем 0<= x,y,z <= 1
x * b1 + y * b2 + z * b3 = c(100, 50)
=>
x * 100 + y * 300 + z * 100 = 100
x * 100 + y * 10 + z * 20 = 50
=>
y = (8*x)/5 -3/5
z = 14/5-(29*x)/5
итд.
Тоже самое для N:
b1, b2, ..bn
x1 * b1 + .+xn * bn = c

Упрощенный (т.е без отдельного ввода) пример программирования ограничениями:
http://pastebin.com/zRQrVR2m
SWI пролог (просто там библиотека уже встроенна да и ввод с клавиатуры "встроен" ;) )
решения:
?- solve([bottle(b1,(100:100)), bottle(b2, (300:10)),bottle(b3, (100:20))], coctail(100:50),R).
R = [result(b1, 14 rdiv 29), result(b2, 5 rdiv 29), result(b3, 0)] ;
R = [result(b1, 14 rdiv 29), result(b2, 5 rdiv 29), result(b3, 0)] ;
R = [result(b1, 3 rdiv 8), result(b2, 0), result(b3, 5 rdiv 8)] ;
rdiv = "дробь".
Т.е первое решение:14/29 cодержимого первой бутылки и 5/29 второй.

Получаем сферического коня в вакууме, которым невозможно пользоваться на практике (требует абсолютной точности разлива, да и как скажем отмерять 137/311-тых ?)
==========
В принципе, можно поизвращаться с дополнительными условиями:
Т.е пользоватся условными единицами и добавить некоторые ограничения:
x1 * b1 + x2 * b2 + .xn * bn == c(AlcSum,SugSum)
и
x1 * b1, x2 *b2 .. xn*bn : нат. числа.
==========
На практике опять получится конь. Треугольный, в невесомости.
Ибо все вполне может закончится банальным "полным" перебором (зависит конечно от конекретной библиотеки - но в них все же ИИ не встроен) - а это для более менее больших N не особо приемлимо.

Практичное, работающее решение: работаем с дробями, округляем в конце (жертвуя точностью)
Тут и пару условий добавить можно - ничего страшного не случится.
код
http://pastebin.com/yKg0pDnY

возможные решения:
формат:
ввод: cписок_бутылок[(спирт:сахар),(спирт:cахар) ...] в условных единицах
в ответе выводится полученый вариант коктейля (спирт:cахар) и сколько у.е нужно налить из соотв. бутылки.

?- solve([100:100, 300:10, 100:20], coctail(100:50),R).
R = result(100.758:50.2419):liquid-from-bottle([97, 54, 0]) ;
R = result(100.0:50.0):liquid-from-bottle([75, 0, 75]) ;

?- solve([100:100, 300:10, 100:20], coctail(100:80),R).
R = result(100.79:80.2097):liquid-from-bottle([159, 22, 0]) ;
R = result(100.0:80.0):liquid-from-bottle([150, 0, 30]) ;

?- solve([100:100, 300:10, 100:20], coctail(100:4),R).
R = result(100.677:4.32258):liquid-from-bottle([2, 103, 0]) ;
R = result(100.941:4.05914):liquid-from-bottle([0, 100, 5]) ;

?- solve([99:1, 90:10, 80:20], coctail(85:15),R).
R = result(85.93:15.07):liquid-from-bottle([27, 0, 74]) ;
R = result(85.0:15.0):liquid-from-bottle([0, 50, 50]) ;

?- solve([1013:59, 1093:137, 1451:311, 1319:7, 1009:271, 1747:557, 1361:307,1741:223, 929:67,1229:131], coctail(5093:557),R).
R = result(5093.88:557.125):liquid-from-bottle([1072, 1230, 1762, 1326, 177, 0, 0, 0, 84, 0]) ;
R = result(5093.99:557.01):liquid-from-bottle([1072, 1230, 1282, 707, 0, 0, 0, 0, 0, 1360]) ;
ВД
Владимир Дубровин
2 026
Лучший ответ
гыгы.. 3 бутылки?.. так мало же:))
Саша Фон
Саша Фон
74 261
Если бы был один параметр, то было бы проще. А так - рекурсивный перебор.
Могу за вас написать, если хотите.
Тоо Феб-С
Тоо Феб-С
34 701

Похожие вопросы