Форум программистов, компьютерный форум, киберфорум
Turbo Pascal
Войти
Регистрация
Восстановить пароль
Карта форума Темы раздела Блоги Сообщество Поиск Заказать работу  
 
Рейтинг 4.83/6: Рейтинг темы: голосов - 6, средняя оценка - 4.83
1 / 0 / 0
Регистрация: 22.07.2014
Сообщений: 8
1

Как максимально можно наполнить сосуд V с помощью маленьких сосудов?

04.08.2014, 00:38. Показов 1181. Ответов 16
Метки нет (Все метки)

Author24 — интернет-сервис помощи студентам
Есть большой сосуд вместимостью V литров. Есть N маленьких сосудов вместимостью а1, а2, ..., аN литров. Как максимально можно наполнить сосуд V с помощью маленьких сосудов. (Учитывая то, что зачерпывать маленькие сосуды нужно полностью) (V <= 10000, N <= 500, ai <= 10000)

Не могу понять как это можно решить, может у кого-то будут какие-нибудь идеи?
0
Programming
Эксперт
94731 / 64177 / 26122
Регистрация: 12.04.2006
Сообщений: 116,782
04.08.2014, 00:38
Ответы с готовыми решениями:

Как можно быстро наполнить данными справочник географических названий?
Доброго времен суток. В институте появилась задача - создать в имеющейся БД таблицу - справочник...

Сосуд разделен подвижным поршнем. В каком отношении поршень будет делить сосуд, если его меньшую часть нагреть?
В закрытом цилиндрическом сосуде постоянного сечения находится газ при нормальных условиях. Сосуд...

Установить, можно ли перелить воду из банки в один из указанных сосудов
Известна вместимость стакана S, бокала B и кружки K (S+B+K&lt;=1000 мл). В литровую банку налито V мл...

Как можно в памяти уместить больше данных ?Большой массив или список маленьких массивов ?
сабж выше

16
2509 / 1130 / 582
Регистрация: 07.06.2014
Сообщений: 3,286
04.08.2014, 11:46 2
мысли вслух...

я бы предложил решение перебором - нахождение MAX( подсумм (a1... an)<=V)
Но N может быть 500, это очень много, поэтому, я не уверен, что решение перебором пройдёт по времени...
1
1 / 0 / 0
Регистрация: 22.07.2014
Сообщений: 8
04.08.2014, 16:12  [ТС] 3
Sergio Leone, маленькие сосуды можно использовать много раз, а ограничение по времени 2 секунды
0
0 / 0 / 0
Регистрация: 04.08.2014
Сообщений: 5
05.08.2014, 12:42 4
Не совсем понятно условие..
Если гарантированно можно заполнить сосуд, то один из вариантов может быть таков.. (только ловить правильную последовательность и выходить)

Pascal
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
var
    a : array[1..500] of LongInt;
    s : array[1..10000] of LongInt;
    n : LongInt;
 
procedure P(v, k, m : LongInt);
var
    i : LongInt;
begin
    if (k > n) or (v <= 0) then begin
        if v = 0 then begin
            for i := 1 to m-1 do
                Write(s[i], ' ');
            WriteLn
        end;
        Exit
    end;
 
    s[m] := a[k];
    P(v-a[k], k, m+1);
    P(v, k+1, m)
end;
 
var
    v, i : LongInt;
begin
    ReadLn(v, n);
    for i := 1 to n do Read(a[i]);
 
    P(v, 1, 1)
end.
Как максимально можно наполнить сосуд V с помощью маленьких сосудов?
Подразумевается, что для теста 10 3 7 8 9 нужно вывести 9?
0
2509 / 1130 / 582
Регистрация: 07.06.2014
Сообщений: 3,286
05.08.2014, 13:05 5
Цитата Сообщение от Раут Посмотреть сообщение
Подразумевается, что для теста 10 3 7 8 9 нужно вывести 9?
угу. на мой взгляд, именно 9

Добавлено через 57 секунд

Не по теме:

Раут, подскажите, это ваше решение через динамическое программирование, я правильно понял?

1
0 / 0 / 0
Регистрация: 04.08.2014
Сообщений: 5
05.08.2014, 13:17 6
Цитата Сообщение от Sergio Leone Посмотреть сообщение
Раут, подскажите, это ваше решение через динамическое программирование, я правильно понял?
Нет. Мое решение - это полный перебор. Массив s исключительно для вывода ответа.
0
2509 / 1130 / 582
Регистрация: 07.06.2014
Сообщений: 3,286
05.08.2014, 13:26 7
Цитата Сообщение от Раут Посмотреть сообщение
Нет. Мое решение - это полный перебор. Массив s исключительно для вывода ответа.
ясно. спасибо за ответ.

Думаете, что полный перебор пройдёт по времени при большом N ?

и, кстати, при нахождении решения, когда сумма точно даёт V, перебор нужно прерывать, иначе ваш код продолжает искать ВСЕ возможные варианты: рекурсия есть рекурсия...
1
0 / 0 / 0
Регистрация: 04.08.2014
Сообщений: 5
05.08.2014, 13:34 8
Цитата Сообщение от Sergio Leone Посмотреть сообщение
Думаете, что полный перебор пройдёт по времени при большом N ?
Проблема не в N.. а в самих a[i].. Если они очень малы, то задача решается очень быстро.. Иначе будут проблемы.. Естественно такое решение не пройдет..
и, кстати, при нахождении решения, когда сумма точно даёт V, перебор нужно прерывать, иначе ваш код продолжает искать ВСЕ возможные варианты: рекурсия есть рекурсия...
Именно для вывода ВСЕХ вариантов я и написал выход.. При тесте 1000 500 1 2 3..500 я ждал примерно 30-45 минут.. Результаты выводил в файлик.. Когда его вес стал 57гигов я всё же решил остановиться
0
1 / 0 / 0
Регистрация: 22.07.2014
Сообщений: 8
05.08.2014, 13:40  [ТС] 9
Раут, да, при вашем тесте будет такой ответ, а например при 10 3 8 7 3 будет ответ 10
0
Почетный модератор
64300 / 47595 / 32743
Регистрация: 18.05.2008
Сообщений: 115,181
05.08.2014, 13:51 10
Вопрос
Цитата Сообщение от Evil Nigga Посмотреть сообщение
Как максимально можно наполнить сосуд V с помощью маленьких сосудов.
Ответ
Цитата Сообщение от Evil Nigga Посмотреть сообщение
будет такой ответ, а например при 10 3 8 7 3 будет ответ 10
Не понял...
0
0 / 0 / 0
Регистрация: 04.08.2014
Сообщений: 5
05.08.2014, 13:55 11
Puporev, все просто
Подразумевается, что для теста 10 3 7 8 9 нужно вывести 9?
да,а например при 10 3 8 7 3 будет ответ 10
0
1 / 0 / 0
Регистрация: 22.07.2014
Сообщений: 8
05.08.2014, 13:56  [ТС] 12
Puporev, ну у вас большой сосуд вместимостью 10 и 3 маленьких вместимостями 8, 7 и 3. Т.е. в большой можно влить 7 и 3
0
0 / 0 / 0
Регистрация: 04.08.2014
Сообщений: 5
05.08.2014, 14:20 13
Evil Nigga, а откуда задача? Есть ли он на каком-нить ресурсе с тестирующей системой?

ИМХО, задачу нельзя решить динамическим программированием..
Поэтому только полный перебор..
0
266 / 192 / 50
Регистрация: 16.06.2014
Сообщений: 424
27.08.2014, 23:26 14
А разве это не рюкзак? ДП
2
2509 / 1130 / 582
Регистрация: 07.06.2014
Сообщений: 3,286
28.08.2014, 09:00 15
Цитата Сообщение от Iriini Посмотреть сообщение
ДП
что-то мне это ДП не даётся... Кроме задач с черепашкой, другие как-то в голове не укладываются...
Iriini, если Вам не сложно, можете рассказать про алгоритм решения данной задачи через Динамическое Программирование ?
Какую функцию построить, как хранить...
Ну или, если Вам проще - пример программы (можно даже не рабочий, но с комментами).

Заранее большое спасибо!
0
266 / 192 / 50
Регистрация: 16.06.2014
Сообщений: 424
28.08.2014, 16:57 16
Sergio Leone, мне нравятся разборы ИТМО
http://neerc.ifmo.ru/wiki/inde... 0%BA%D0%B5
Над этой конкретно задачей с точки зрения рюкзака надо еще подумать
2
191 / 161 / 116
Регистрация: 14.09.2013
Сообщений: 302
28.08.2014, 23:55 17
Pascal
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
var
  V, N, i, j, m: integer;
  a: array[0..501] of integer;
  x: array[0..501, 0..10001] of integer;
  
begin
  readln(V, N);
  for i := 1 to N do
    for j := 0 to V do
      x[i, j] := 0;
  for i := 1 to N do
    read(a[i]);
  for i := 1 to N do
    for j := 0 to V do
      begin
        x[i, j] := x[i - 1, j];
        for m := j div a[i] downto 1 do
          if x[i, j] < x[i - 1, j - m * a[i]] + m * a[i]
            then x[i, j] := x[i - 1, j - m * a[i]] + m * a[i]
      end;
  writeln(x[N, V])
end.
1
28.08.2014, 23:55
IT_Exp
Эксперт
87844 / 49110 / 22898
Регистрация: 17.06.2006
Сообщений: 92,604
28.08.2014, 23:55
Помогаю со студенческими работами здесь

Как можно оптимизировать ASP максимально?
Имеется система заказа, реализована на ASP а база на Оракле v7 одновременно заказ выполняют в час...

Найти количество коробочек, которые можно наполнить теми цифрами по 5 шт
Мне нужна программа, которая получает цифры от пользователя, а выдает кол-во коробочек, которые...

Как определять, сколько максимально потоков можно запускать?
Здравствуйте. Есть класс. Он накапливает в себе задания на отправку запросов, а потом разом,...

Не работает вся оперативка и как можно максимально ускорить данный ПК
Всем привет! :) Друзья, подскажите пожалуйста новичку - почему комп не использует всю оперативку?...


Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
17
Ответ Создать тему
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin
Copyright ©2000 - 2024, CyberForum.ru