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

Обратная задача о ранце (ДП) - C++

Восстановить пароль Регистрация
Другие темы раздела
C++ Присвоить Указателю адрес из массива Char http://www.cyberforum.ru/cpp-beginners/thread864314.html
Например есть такой код: #include <iostream> using namespace std; int main() { int a = 123456789; int *sa = &a;
C++ Вычислить значения заданной функции для заданных значений аргумента Здравствуйте, если у вас есть примеры решенного, либо вы знаете как удовлетворить условия, то помоги. Задание: Дана формула и ряд для вычисления значения функции. Разработать программу (схемы алгоритмов) для вычисления значений заданной функции для заданных значений аргумента с заданной точностью и вывода значений аргумента и функции в табличной форме. Вычисление значений заданной функции... http://www.cyberforum.ru/cpp-beginners/thread864308.html
C++ Изменение цвета строки!
доброго времени суток! вот условие задачи: Написать программу “Прыгающий шарик”. После запуска программы на экране должна отображаться отцентрированная текстовая строка, а также шарик, прыгающий по буквам строки по траектории в виде полукруга. При движении шарик вызывает изменение цвета текущей буквы, а также выдачу короткого звукового сигнала. Программа должна позволять пользователем вводить...
C++ Сравнение элементов списка
Помогите написать функцию, которая проверяет истинность утверждения, что каждый элемент из первого списка является элементом из второго. #include <iostream> #include <fstream> #include <locale.h> using namespace std;
C++ Описание функции ungetch() http://www.cyberforum.ru/cpp-beginners/thread864245.html
Привет всем! Такой вопрос, я наткнулся на функцию ungetch(с), прочитал описание "возвращает символ в буфер" но я не могу понять, как же она работает, и что она делает?
C++ сортировка связного списка Привет всем! пришлите пожалуйста код реализации сортировки односвязного списка (желательно с комментарием)! а то у меня совсем ничего неполучается... подробнее

Показать сообщение отдельно
El studentos
0 / 0 / 0
Регистрация: 15.10.2012
Сообщений: 5
16.05.2013, 07:51  [ТС]     Обратная задача о ранце (ДП)
Цитата Сообщение от Ternsip Посмотреть сообщение
El studentos, постановка задачи во втором пункте некорректна, мне непонятно следующее : Нужно набрать max стоимость <= M, но их всех таких наборов, которые дают этот вес, нужно выбрать такой, что в нём больше монет ?

El studentos, кстати, первую задачу я раньше решал вот так :
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
#include <iostream>
#include <vector>
#include <limits>
 
using namespace std;
 
int main(){         
    vector <int> ranec(1001, -INT_MAX);
    ranec[0] = 0;
    int n, q;
    cin >> n >> q;
    for (int i = 0; i < n; i++){
        int w, c;
        cin >> w >> c;
        for (int j = q - w; j >= 0; j--){
            if (ranec[j] != -INT_MAX){
                ranec[j + w] = max(ranec[j + w], ranec[j] + c);
            }
        }
    }
    int ans = 0;
    for (int j = 0; j <= q; j++){
            ans = max(ranec[j], ans);
    }
    cout << ans;
    return 0;
}
Нужно набрать предметов к примеру на 10кг, при их наименьшем весе.

К примеру есть предметы
вес | ценность
3 | 5
2 | 4
5 | 5
4 | 1

Нужно набрать на 10 монет, при минимальном весе набора.
Сейчас у нас есть варианты для набора: 1-3, 1-2-4, 2-3-4, соответсвенно минимальный вес из данных наборов будет равен 8, т.е. набор 1-3.

Задача такова)
 
Текущее время: 20:16. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2016, vBulletin Solutions, Inc.
Рейтинг@Mail.ru