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

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

Восстановить пароль Регистрация
 
Никита Однороб
107 / 87 / 13
Регистрация: 21.08.2012
Сообщений: 352
11.07.2015, 22:43     Динамическое программирование - нужно отследить подходящие элементы #1
Мне нужна задача, которую, в принципе, можно назвать "облегченной задачей о ранце". Я ввожу выдерживаемый вес ранца, а на следующей строке - вес предметов (цифра 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";
}
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
11.07.2015, 22:43     Динамическое программирование - нужно отследить подходящие элементы
Посмотрите здесь:

C++ Динамическое программирование
Динамическое программирование C++
C++ Динамическое программирование
C++ Динамическое программирование
C++ ДП Динамическое программирование
C++ Динамическое программирование
C++ Динамическое программирование
C++ Динамическое программирование!

Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
Ответ Создать тему
Опции темы

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