Форум программистов, компьютерный форум CyberForum.ru
Наши страницы

Задача типа Водолей - C++

Войти
Регистрация
Восстановить пароль
Другие темы раздела
C++ Выполнить сортировку массивов А и В по возрастанию с использованием сортировки Шелла.(Паскаль) http://www.cyberforum.ru/cpp-beginners/thread1043305.html
Сортировать массивы А и В по возрастанию с использованием сортировки Шелла. Узнать сумма максимальных элементов массивов С и D. Размерность : A: 23 B: 14 C: 18 D: 22 Диапазон...
C++ Задача на структуры В техническом центре по ремонту автомобилей в течении недели(6 рабочих дней) израсходованы различные детали 8-ми наименований. Известны наименование каждого вида детали, их цена и количество деталей,... http://www.cyberforum.ru/cpp-beginners/thread1043292.html
C++ односторонний список. не могу написать в) и дописать б)
Використовувати (лінійні) односпрямовані списки без заголовної ланки (мал. а) або з заголовною ланкою (мал. б) при наступному їхньому описі typedef char ТЕ ; struct ланка { ТЕ елем; ланка*...
C++ Разработайте программу, которая вводит 10 натуральных чисел с проверкой правильности ввода
Доброго времени суток) Помогите, пожалуйста, сделать задание: Разработайте программу, которая вводит 10 натуральных чисел с проверкой правильности ввода (т.е. каждое вводимое число проверяется,...
C++ Динамический массив http://www.cyberforum.ru/cpp-beginners/thread1043253.html
Как мне в динамическом массиве не удалять весь массив, а только элементы?
C++ Решение задач 1. Решить неравенство a{x}^{2}+bx+c\leq 0. #include <cstdlib> #include <iostream> #include <Math.h> using namespace std; int main(int argc, char *argv) { double a, b, c, x1, x2, p, v, d;... подробнее

Показать сообщение отдельно
azbest
41 / 41 / 8
Регистрация: 12.03.2013
Сообщений: 148

Задача типа Водолей - C++

16.12.2013, 00:55. Просмотров 396. Ответов 0
Метки (Все метки)

Есть задача типа Водолей.

Дано n посудин емкостью по k_1, k_2,...,k_n каждая.
Нужно набрать P литров жидкости.

Допустимые действия:
- набирать воду до упора из бесконечного источника в любой сосуд.
- переливать из любого сосуда в любой пока один из них не будет полным ил пустой.
- выливать воду из сосуда

Найти минимальное количество действий для того чтоб в любом сосуде было нужное количество жидкости.


Подскажите в какую сторону копать. На первый взгляд это поиск в ширину на графе. Но как его организовать (и сам граф и тем более поиск). Перебор кажется не подойдет ибо не известно изначальное количество сосудов.

Если задача слишком сложная можно решить частичный вариант из 3 сосудов

Пример:
3 - сосуда
4 6 9 - их емкости
7 - нужное количество

минимальный твет кажется 4

* 4 6 9
0 0 0 0 (начальное состояние)
1 4 0 0 (наполнить 4-литровый)
2 0 4 0 (перелить из 4 все в 6-литровый)
3 0 4 9 (наполнить 9-литровый)
4 0 6 7 (перелить до заполнения из 9-и в 6-литровый до заполнения)
в 9-литровом профит)
0
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
 
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2017, vBulletin Solutions, Inc.
Рейтинг@Mail.ru