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

Динамическое программирование - нужно отследить подходящие элементы - C++

Восстановить пароль Регистрация
Другие темы раздела
C++ Дерево Хаффмана http://www.cyberforum.ru/cpp-beginners/thread1497410.html
Здравствуйте. Хотел узнать как работает дерево Хаффмана и 4 дня изучал материалы в интернете (статьи, видеоуроки) и т.д.), написал программу, которая кодирует и декодирует по этому алгоритму. Суть вопроса вот в чем: Программа то все делает, но как дать возможность другим программам читать эти самые файлы по алгоритму Хаффмана ? Ну вот я создаю дерево, потом записываю путь к каждому символу в...
C++ Специализация метода темплейтного класса вложенного в темплейтный класс Есть два темплейтных класса template <bool T2> class B { void b(); } template <> void B<true>::b() {} http://www.cyberforum.ru/cpp-beginners/thread1497383.html
OpenGL, трехмерный график OpenGL
Начинаю по чуть-чуть изучать программирование , попалась для меня немного странная задачка , нужно вывести график функции z=cos(r)/r , но при этом r=sqrt((x^2)*(y^2)). выдает много ошибок , прошу помощи в их исправление или советов. #include<openGL/gl.h> #include<Glut/glut.h> #include <math.h> #include <stdlib.h> float f(float x, float y , float r , float z) { return...
C++ Крестики-нолики - алгоритм для игры против ПК
Смотрю, уже только ленивый не сделал. Собственно это я. Вчера сел, написал свои 200 строк какашкокода для любого поля с любым количеством требуемых чисел для победы по всем направлениям.. С победой пришлось повозиться, но все вышло. Собственно, куда смотреть в отношении алгоритма для игры против ПК? Очевидно, что рандом так себе играет. Пока есть следующий вариант: if Проверить возможность...
C++ Запись двумерного массива в файл http://www.cyberforum.ru/cpp-beginners/thread1497325.html
В общем нужно записать двумерный массив в фаил, но что то ни как не получается. //magicQuad.h #ifndef MAGICQUAD_H #define MAGICQUAD_H #include <iostream> using std::cout; using std::endl; class magicQuad {
C++ OpenGL: Вывести значения двух функций Пытаюсь разобраться с opengl , хотел вывести две функции , но выдает ошибку , подскажите как исправить. #include <iostream> #include<openGL/gl.h> #include<Glut/glut.h> void draw() { glClear(GL_COLOR_BUFFER_BIT); glColor3f(1, 0, 0); подробнее

Показать сообщение отдельно
Никита Однороб
107 / 87 / 13
Регистрация: 21.08.2012
Сообщений: 352
11.07.2015, 22:43     Динамическое программирование - нужно отследить подходящие элементы
Мне нужна задача, которую, в принципе, можно назвать "облегченной задачей о ранце". Я ввожу выдерживаемый вес ранца, а на следующей строке - вес предметов (цифра 0 означает окончание ввода). Если у меня вес ранца 5, а предметы весом 2, 2, 2, 1, 1 то я введу
5
2 2 2 1 1 0
Я этим кодом могу узнать только ВОЗМОЖНОСТЬ такого заполнения ранца. Элемент массива dp[i][j] будет true, если с помощью j первых элементов я могу заполнить ранец вместимостью i. Но, из-за недостатка знаний, я не могу реализовать запоминание этих элементов, а это очень нужно. Кто может, помогите пожалуйста!
Вот мой код:
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
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
#include <iostream>
#include <string>
#include <cmath>
#include <algorithm>
 
#define f(i, s, f) for(int i = s; i < f; i++)
#define _f(i, s, f) for(int i = s; i <= f; i++)
 
typedef long long ll;
typedef long double ld;
 
using namespace std;
 
ll v, tmp, tmp2, ottr[1000], k = 0, old_k = 0;
bool dp[1000][1000];
 
void _count() {
    f(i, 0, 1000) f(j, 0, 1000) dp[i][j] = false;
    dp[0][0] = true;
 
    _f(j, 0, k - 1) {
        _f(i, 0, v) {
            if (dp[i][j]) {
                dp[i][j+1] = true;
                if (i + ottr[j] <= v) { dp[i + ottr[j]][j + 1] = true; }
            }
        }
    }
}
 
int main() {
    cin >> v;
 
    while (true) {
        cin >> tmp;
        if (tmp == 0) break;
        ottr[k] = tmp; 
        k++;
    }
 
    if (k > 0) _count();
 
    cout << "OK";
}
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
 
Текущее время: 16:35. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2016, vBulletin Solutions, Inc.
Рейтинг@Mail.ru