Решение задачи о ранце методом динамического программирования

@growssa · Регистрация: 11.10.2020

Студворк — интернет-сервис помощи студентам

Привет всему сообществу. Нужна ваша помощь.
Я совершенно новичок в matlab и математике, задали задачку, где требуется определить, какие предметы и в каком количестве нужно загрузить в ранец, чтобы суммарная ценность груза была максимальной.

Реализовал следующую часть кода:

Matlab M
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
% решение задачи о ранце методом динамического программирования 
disp('введите объём ранца V')
V=input('V=');
disp('введите количество видов предметов n')
n=input('n=');
disp('введите объём (вес) 1ед.предметов каждого вида') 
T1='p(';
for i=1:n
    T_i=num2str(i);
    str1=strcat('v',T_i,'=');
    v(i)=input(str1);
end
disp('введите стоимость 1ед.предметов каждого вида') 
for i=1:n
    T_i=num2str(i); 
    str1=strcat('c',T_i,'=');
    c(i)=input(str1);
end
disp('введите максимальное количество предметов каждого вида') 
for i=1:n

Далее мне помогал преподаватель, но у меня ничего не сработало, так как полного понимания языка matlab нет, особенно интересует последняя строчка. Обращаюсь к вам, дорогие профессионалы, так как преподавателя не понимаю, буду благодарен за любую помощь, спасибо.

Matlab M
1
2
3
4
5
6
7
8
9
10
11
    T_i=num2str(i); 
    str1=strcat('d',T_i,'=');
    d(i)=input(str1);
    if d(i)*v(i) > V
        d(i)=min(d(i),fix(V/v(i)));
        str2=num2str(d(i)); 
        str3=strcat('Поправка: d',T_i,'=',str2); disp(str3)
    end
end
disp('Ввод вх. данных закончен. Нажмите Enter'); pause
[Zmax,X] = sumka(V,n,v,c,d)

@Centurio · 27.11.2022, 07:41

growssa, приведите математическую модель. Она у вас, видимо, записана в m-функции sumka, которую вы сюда не выложили.
Во второй части кода условие if можно убрать, вместо него оставить только строку 5.

@growssa · 27.11.2022, 08:08 **[ТС]**

Centurio,
Математическая модель задачи выглядит так->
640X_1+ 870X_2+350X_3+480X_4→max
120X_1+ 150X_2+90X_3+100X_4≤990
0≤ X_i≤10 (i=1,…4)целые.

@Centurio · 27.11.2022, 09:52

growssa, это-то понятно, можно и линейным программированием решить. Но вам надо динамическое программирование, ход которого в функции sumka, вероятно, прописан. Но вы эту функцию до сих пор не показали.

@growssa · 27.11.2022, 10:34 **[ТС]**

оу, извините, Centurio, я настолько необразован в данной теме, что сначала не заметил, что код по факту подразумевает только ввод данных)) ход функции sumka не прописан, с этим и возникли проблемы, буду думать как ее реализовать

Новые блоги и статьи Все статьи Все блоги /
Мысли в слух. Про "навсегда". kumehtar 16.04.2026 Подумалось тут, что наверное очень глупо использовать во всяких своих установках понятие "навсегда". Это очень сильное понятие, и я только начинаю понимать край его смысла, не смотря на то что давно. . .	My Business CRM MaGz GoLd 16.04.2026 Всем привет, недавно возникла потребность создать CRM, для личных нужд. Собственно программа предоставляет из себя базу данных клиентов, в которой можно фиксировать звонки, стадии сделки, а также. . .	Знаешь почему 90% людей редко бывают счастливыми? kumehtar 14.04.2026 Потому что они ждут. Ждут выходных, ждут отпуска, ждут удачного момента. . . а удачный момент так и не приходит.	Фиксация колонок в отчете СКД Maks 14.04.2026 Фиксация колонок в СКД отчета типа Таблица. Задача: зафиксировать три левых колонки в отчете. Процедура ПриКомпоновкеРезультата(ДокументРезультат, ДанныеРасшифровки, СтандартнаяОбработка) / / . . .
Настройки VS Code Loafer 13.04.2026 { "cmake. configureOnOpen": false, "diffEditor. ignoreTrimWhitespace": true, "editor. guides. bracketPairs": "active", "extensions. ignoreRecommendations": true, . . .	Оптимизация кода на разграничение прав доступа к элементам формы Maks 13.04.2026 Алгоритм из решения ниже реализован на нетиповом документе, разработанного в конфигурации КА2. Задачи, как таковой, поставлено не было, проделанное ниже исключительно моя инициатива. Было так:. . .	Контроль заполнения и очистка дат в зависимости от значения перечислений Maks 12.04.2026 Алгоритм из решения ниже реализован на примере нетипового документа "ПланированиеПерсонала", разработанного в конфигурации КА2. Задача: реализовать контроль корректности заполнения дат назначения. . .	Архитектура слоя интернета для сервера-слоя. Hrethgir 11.04.2026 В продолжение https:/ / www. cyberforum. ru/ blogs/ 223907/ 10860. html Знаешь что я подумал? Раз мы все источники пишем в голове ветки, то ничего не мешает добавить в голову такой источник, который сам. . .

@Centurio Модератор 1765 / 1610 / 541 Регистрация: 13.09.2015 Сообщений: 5,630
	27.11.2022, 07:41
	growssa, приведите математическую модель. Она у вас, видимо, записана в m-функции sumka, которую вы сюда не выложили. Во второй части кода условие if можно убрать, вместо него оставить только строку 5. 0

@growssa 0 / 0 / 0 Регистрация: 11.10.2020 Сообщений: 11
	27.11.2022, 08:08 [ТС]
	Centurio, Математическая модель задачи выглядит так-> 640X_1+ 870X_2+350X_3+480X_4→max 120X_1+ 150X_2+90X_3+100X_4≤990 0≤ X_i≤10 (i=1,…4)целые. 0

@Centurio Модератор 1765 / 1610 / 541 Регистрация: 13.09.2015 Сообщений: 5,630
	27.11.2022, 09:52
	growssa, это-то понятно, можно и линейным программированием решить. Но вам надо динамическое программирование, ход которого в функции sumka, вероятно, прописан. Но вы эту функцию до сих пор не показали. 0

@growssa 0 / 0 / 0 Регистрация: 11.10.2020 Сообщений: 11
	27.11.2022, 10:34 [ТС]
	оу, извините, Centurio, я настолько необразован в данной теме, что сначала не заметил, что код по факту подразумевает только ввод данных)) ход функции sumka не прописан, с этим и возникли проблемы, буду думать как ее реализовать 0