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

Динамическое программирование. Вложенные коробки. - C++

Войти
Регистрация
Восстановить пароль
Другие темы раздела
C++ Как подсчитать количество вхождений подстроки в строку http://www.cyberforum.ru/cpp-beginners/thread229793.html
Добрый вечер! Как можно подсчитать количество вхождений строки S2 в строку S1? Допустим: S1= dfsgsffgsrr S2= gs
C++ Количество слов и цифр в строке, и последовательность Помогите, осталось решить всего 2 задачи из 10 заданных)) :) Нужно дописать решение, но чтобы его принимал компилятор BORLANDC, потому что сдаем пока только на нём. В первой задание: Сколько слов и цифр в строке? Написал, как найти количество слов, но как вычислите количество цифр? //254(3).cpp #include <stdio.h> #include <conio.h> enum {OUT, IN}; http://www.cyberforum.ru/cpp-beginners/thread229784.html
C++ Составить фрагмент программы
С коментприями, если можна!!!
C++ Составить программу
С коментприями
C++ Составить фрагмент программы http://www.cyberforum.ru/cpp-beginners/thread229756.html
С коментприями, если можна
C++ Составить фрагмент программы!!! С коментприями подробнее

Показать сообщение отдельно
valeriikozlov
Эксперт C++
4667 / 2493 / 321
Регистрация: 18.08.2009
Сообщений: 4,550
17.01.2011, 09:08     Динамическое программирование. Вложенные коробки.
Цитата Сообщение от opax Посмотреть сообщение
не могли бы вы накидать динамический способ реализации ?..
Накидываю:
Создаете стурктуру коробки, которая включает в себя:
- длина стороны A
- длина стороны B
- длина стороны C (заполнять данных о сторонах нужно так: A - самое максимальное, B - меньше или равно A, С - меньше или равно B)
- объем коробки (вычисляется при заполнении из данных о сторонах) (V)
- номер индекса коробки с которой есть связь (далее подробней объясню) (Num)
- максимальный объем всех вложенных коробок (далее подробней объясню) (Max_V)
- номер самой коробки (нужно, если требуется в конце программы вывести номера коробок)
Далее можно так:
Создаем массив размером N (количество коробок) для хранения типа созданной структуры. Считываем данные в этот массив (длины сторон), расчитываем сразу объем коробок, при необходимости проставляем номера коробок.
Далее сортируем этот массив по убыванию сторон так:
if(mas[i].A<mas[i+1].A ||
(mas[i].A==mas[i+1].A && mas[i].B<mas[i+1].B)
|| (mas[i].A==mas[i+1].A && mas[i].B==mas[i+1].B && mas[i].C<mas[i+1].C))
// то меняем местами mas[i] и mas[i+1]
После сортировки делаем: mas[N-1].Max_V=mas[N-1].V; mas[N-1].Num=N;

Далее сама динамика. Перебираем элементы массива от N-2 до 0. Для каждого очередного элемента массива делаем следующее:
- mas[i].Num=N; mas[i].Max_V=mas[i].V;
- затем просматриваем элементы правее очередного. Если какой-то элемент помещается в очередной (это проверяется так: if(mas[i].A>mas[j].A && mas[i].B>mas[j].B && mas[i].C>mas[j].C)), и при этом mas[i].Max_V<mas[j].Max_V+mas[i].V , то делаем так: mas[i].Max_V=mas[j].Max_V+mas[i].V; mas[i].Num=j;
После этого прохода ищем элемент с максимальным значением mas[i].Max_V . Это и есть значение максимального суммарного объема. Что бы вывести коробки, которые вложены, используем значение mas[i].Num .
 
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2017, vBulletin Solutions, Inc.
Рейтинг@Mail.ru