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

Задача о рюкзаке - C++

Войти
Регистрация
Восстановить пароль
Другие темы раздела
C++ Программа читает свой текст и обрабатывает его по заданному в варианте условию http://www.cyberforum.ru/cpp-beginners/thread74917.html
написать программу, которая читает свой текст и обрабатывает его по заданному в варианте условию. Результаты обработки записать в фаил output.txt Условие: посчитать кол-во переменных типа int
C++ Машина Тьюринга, определение вхождения подстроки в строку приветствую. собственно, задание по мт. вопрос не по части решения теоретического, а именно по реализации на c++. на вход мт поступает строка, состоящая из символов a, b или c. построить мт, которая определяет вхождение подстроки 'abc' в исходную задаваемую строку. по окончании работы мт на ленте должна быть записана исходная строка и после * слова 'YES' или 'NO' (в зависимости от того,... http://www.cyberforum.ru/cpp-beginners/thread74913.html
C++ Контрольная работа(( проверь свои знания):D
помогите пожалуйста сделать контрольную работу, мне нада сделать её хорошо или незачёт((( очень прошу... я в классах ниочём( Задача 1. Разработать класс для представления несократимой дроби, задаваемой двумя полями целого типа (числитель и знаменатель). Класс должен включать весь необходимый интерфейс: конструкторы, перегрузку операций (в том числе + и =), другие необходимые методы....
Полный дек C++
Добрый день! мучаюсь с задачей - реализовать тип и функции (инициализация,добавление\извлечение элементов с обеих сторон,проверка на пустоту) для реализации полного дека в связной памяти на чистом Си. единственное, что удалось узнать у преподавателя это то,что полный дек нужно создавать на основе двусвязного списка. Подскажите пожалуйста материалы и примеры на эту тему. хочется разобраться а...
C++ 2мерный массив http://www.cyberforum.ru/cpp-beginners/thread74888.html
Путём перестановки элементов квадратной вещественной матрицы добиться того, чтобы её максимальный элемент находился в левом верхнем углу, следующий по величине - в позиции (2,2), следующий по величине - в позиции (3,3) и т.д., заполнив таким образом всю главную диагональ; и найти номер первой из строк, не содержащих не одного положительного элемента.
C++ Ассортимент на тему "функции" Привет всем программистам ;)!..Скажите. а решённые задачки здесь как-нибудь отсортированы?а-то хотедось бы найти задачи на тему 2функции" и посмотреть , как они решаются))) подробнее

Показать сообщение отдельно
Red Planet
49 / 10 / 2
Регистрация: 20.09.2009
Сообщений: 263

Задача о рюкзаке - C++

15.12.2009, 19:14. Просмотров 3585. Ответов 2
Метки (Все метки)

Доброго вечера! Даны n типов предметов, каждый тип обладает своей стоимостью и весом, а также предел грузоподъемности limit. Нужно набрать максимум стоимости и не превысить грузоподъемность. За состояние на каждом шаге принимаем уже израсходованный ресурс.

На n-ом можем взять столько предметов n-ого типа, сколько захотим, лишь бы только не превысить грузоподъемность. На первом это количество равно (limit/mas1)+1, где mas1 - масса 1-ого предмета, единицу прибавляем, так как можем и не брать данный предмет.

Идеи пока что следующие.
1. Делаем class thing, объектом такого класса будет являться наш предмет, имеющий две характеристики: массу и стоимость.
2. Делаем динамический двумерный массив типа thing, где количество столбцов - количество типов предметов, а строки на каждом шаге определяются динамически.

Пример
Три типа предметов, указаны: масса (стоимость). 20 (15), 30 (20), 35 (40). Грузоподъемность 60.

Начинаем работать в прямом направлении слкедующим образом:

http://savepic.ru/978525m.jpg

На каждом шаге отсеиваем неоптимальные траектории. Допустим, на i-ом шаге имеются два пути, сходищихся в одной точке - 20 (30) и 20 (35), в этом случае все продолжения 20 (30) не рассматриваем, т. к. 30<35.

Насчет программной реализации. Предлагается хранить не сами состояния, а траектории (насколько я придумал, создается двумерный массив типа thing (класс определен выше), 8 столбцов, а вот число строк определяется динамически, т. е. на каждом шаге оно разное, в зависимости от количества состояний, сразу вопрос: как это сделать?), На последнем (в примере на третьем шаге просто ищем состояние я максимальной стоимостью, оно и будет являться ответом)

Буду благодарен за помощь в решении.
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
 
Текущее время: 07:36. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2017, vBulletin Solutions, Inc.
Рейтинг@Mail.ru