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

@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 не прописан, с этим и возникли проблемы, буду думать как ее реализовать

Новые блоги и статьи Все статьи Все блоги /
SDL3 для Web (WebAssembly): Обработчик клика мыши в браузере ПК и касания экрана в браузере на мобильном устройстве 8Observer8 02.02.2026 Содержание блога Для начала пошагово создадим рабочий пример для подготовки к экспериментам в браузере ПК и в браузере мобильного устройства. Потом напишем обработчик клика мыши и обработчик. . .	Философия технологии iceja 01.02.2026 На мой взгляд у человека в технических проектах остается роль генерального директора. Все остальное нейронки делают уже лучше человека. Они не могут нести предпринимательские риски, не могут. . .	SDL3 для Web (WebAssembly): Вывод текста со шрифтом TTF с помощью SDL3_ttf 8Observer8 01.02.2026 Содержание блога В этой пошаговой инструкции создадим с нуля веб-приложение, которое выводит текст в окне браузера. Запустим на Android на локальном сервере. Загрузим Release на бесплатный. . .	SDL3 для Web (WebAssembly): Сборка C/C++ проекта из консоли 8Observer8 30.01.2026 Содержание блога Если вы откроете примеры для начинающих на официальном репозитории SDL3 в папке: examples, то вы увидите, что все примеры используют следующие четыре обязательные функции, а. . .
SDL3 для Web (WebAssembly): Установка Emscripten SDK (emsdk) и CMake для сборки C и C++ приложений в Wasm 8Observer8 30.01.2026 Содержание блога Для того чтобы скачать Emscripten SDK (emsdk) необходимо сначало скачать и уставить Git: Install for Windows. Следуйте стандартной процедуре установки Git через установщик. . . .	SDL3 для Android: Подключение Box2D v3, физика и отрисовка коллайдеров 8Observer8 29.01.2026 Содержание блога Box2D - это библиотека для 2D физики для анимаций и игр. С её помощью можно определять были ли коллизии между конкретными объектами. Версия v3 была полностью переписана на Си, в. . .	Инструменты COM: Сохранение данный из VARIANT в файл и загрузка из файла в VARIANT bedvit 28.01.2026 Сохранение базовых типов COM и массивов (одномерных или двухмерных) любой вложенности (деревья) в файл, с возможностью выбора алгоритмов сжатия и шифрования. Часть библиотеки BedvitCOM Использованы. . .	SDL3 для Android: Загрузка PNG с альфа-каналом с помощью SDL_LoadPNG (без SDL3_image) 8Observer8 28.01.2026 Содержание блога SDL3 имеет собственные средства для загрузки и отображения PNG-файлов с альфа-каналом и базовой работы с ними. В этой инструкции используется функция SDL_LoadPNG(), которая. . .

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

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