Форум программистов
 

Восстановите пароль или Зарегистрируйтесь на форуме, о проблемах и с заказом рекламы пишите сюда - alarforum@yandex.ru, проверяйте папку спам!

Вернуться   Форум программистов > Delphi программирование > Паскаль, Turbo Pascal, PascalABC.NET
Регистрация

Восстановить пароль
Повторная активизация e-mail

Купить рекламу на форуме - 42 тыс руб за месяц

Ответ
 
Опции темы Поиск в этой теме
Старый 09.08.2014, 23:30   #1
Evil Nigga
 
Регистрация: 08.08.2014
Сообщений: 7
По умолчанию Непрерывный рюкзак

Перекупщик закупается на оптовой базе. Он может количество товара весом не более W. На базе N товаров весом с1, с2, ...,cn. Kоличество товара каждого типа на базе не ограниченно. Нужно найти максимальный вес который он сможет увезти.

Пример:

Входные:
10
3
1 2 5
Выходные:
10

Входные:
19
2
5 3
Выходные:
18

Последний раз редактировалось Evil Nigga; 09.08.2014 в 23:39.
Evil Nigga вне форума Ответить с цитированием
Старый 10.08.2014, 08:12   #2
Smitt&Wesson
Старожил
 
Аватар для Smitt&Wesson
 
Регистрация: 31.05.2010
Сообщений: 13,964
По умолчанию

Топаем сюда, качаем и решаем методами линейного программирования.
Пиши пьяным, редактируй трезвым.
Справочник по алгоритмам С++ Builder
Smitt&Wesson вне форума Ответить с цитированием
Старый 10.08.2014, 21:49   #3
Poma][a
Новичок
Джуниор
 
Регистрация: 11.10.2011
Сообщений: 3,882
По умолчанию

Цитата:
Входные:
19
2
5 3
Выходные:
18
Как и почему?
5+5+3+3
Мое решение :
Код:
uses Math;

var
	n, m, i, j, k : LongInt;
	w : array [1..100] of LongInt;
	a : array [0..100, 0..10000] of LongInt;

begin
	ReadLn(m, n);
	for i := 1 to n do Read(w[i]);

	for i := 1 to n do
		for j := 0 to m do begin
			a[i, j] := a[i-1, j];
			for k := j div w[i] downto 1 do 
				a[i, j]	:= Max(a[i, j], a[i-1, j-k*w[i]]+k*w[i])
		end;

	WriteLn(a[n, m])
end.
Poma][a вне форума Ответить с цитированием
Старый 10.08.2014, 22:02   #4
Evil Nigga
 
Регистрация: 08.08.2014
Сообщений: 7
По умолчанию

Poma][a, ниже

Последний раз редактировалось Evil Nigga; 10.08.2014 в 22:14.
Evil Nigga вне форума Ответить с цитированием
Старый 10.08.2014, 22:13   #5
Evil Nigga
 
Регистрация: 08.08.2014
Сообщений: 7
По умолчанию

Цитата:
Сообщение от Poma][a Посмотреть сообщение
Как и почему?
5+5+3+3
5+5+5+3 = 18
Evil Nigga вне форума Ответить с цитированием
Старый 10.08.2014, 22:38   #6
Poma][a
Новичок
Джуниор
 
Регистрация: 11.10.2011
Сообщений: 3,882
По умолчанию

555333 <= 19
Poma][a вне форума Ответить с цитированием
Старый 10.08.2014, 23:02   #7
Evil Nigga
 
Регистрация: 08.08.2014
Сообщений: 7
По умолчанию

Цитата:
Сообщение от Poma][a Посмотреть сообщение
555333 <= 19
что это значит?
Evil Nigga вне форума Ответить с цитированием
Старый 10.08.2014, 23:32   #8
Poma][a
Новичок
Джуниор
 
Регистрация: 11.10.2011
Сообщений: 3,882
По умолчанию

Это значит, что я писал с планшета и мне было очень лень ставить плюсики между цифирками.. и еще, что я ошибся на одну 5-ку..
5+5+3+3+3 = 19
19 <= 19
Поэтому ответ НЕ 18
Poma][a вне форума Ответить с цитированием
Старый 10.08.2014, 23:43   #9
Evil Nigga
 
Регистрация: 08.08.2014
Сообщений: 7
По умолчанию

Цитата:
Сообщение от Poma][a Посмотреть сообщение
Это значит, что я писал с планшета и мне было очень лень ставить плюсики между цифирками.. и еще, что я ошибся на одну 5-ку..
5+5+3+3+3 = 19
19 <= 19
Поэтому ответ НЕ 18
простите, вы правы
это я тест не так списал
19
2
3 15

спасибо вам
Evil Nigga вне форума Ответить с цитированием
Ответ


Купить рекламу на форуме - 42 тыс руб за месяц

Опции темы Поиск в этой теме
Поиск в этой теме:

Расширенный поиск


Похожие темы
Тема Автор Раздел Ответов Последнее сообщение
0-1 рюкзак: наибольший вес Evil Nigga Паскаль, Turbo Pascal, PascalABC.NET 3 09.08.2014 12:50
Поиск по всей таблице непрерывный Cyclops БД в Delphi 1 13.08.2012 13:25
Знаменитая задача про рюкзак:\ Duragon Помощь студентам 1 20.06.2011 11:02
Рюкзак на Delphi serg268 Помощь студентам 3 23.09.2010 14:50
Непрерывный звук в системнике Utkin Компьютерное железо 9 17.12.2009 06:49