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

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

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

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

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

15.12.2009, 19:14. Просмотров 3720. Ответов 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 столбцов, а вот число строк определяется динамически, т. е. на каждом шаге оно разное, в зависимости от количества состояний, сразу вопрос: как это сделать?), На последнем (в примере на третьем шаге просто ищем состояние я максимальной стоимостью, оно и будет являться ответом)

Буду благодарен за помощь в решении.
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
 
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2017, vBulletin Solutions, Inc.
Рейтинг@Mail.ru