Форум программистов, компьютерный форум, киберфорум
Наши страницы

С++ для начинающих

Войти
Регистрация
Восстановить пароль
 
Никита Однороб
109 / 89 / 13
Регистрация: 21.08.2012
Сообщений: 364
#1

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

11.07.2015, 22:43. Просмотров 294. Ответов 0
Метки нет (Все метки)

Мне нужна задача, которую, в принципе, можно назвать "облегченной задачей о ранце". Я ввожу выдерживаемый вес ранца, а на следующей строке - вес предметов (цифра 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";
}
0
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
11.07.2015, 22:43
Я подобрал для вас темы с готовыми решениями и ответами на вопрос Динамическое программирование - нужно отследить подходящие элементы (C++):

Динамическое программирование - C++
Усложнили задачу мне.... : Дан массив A. Необходимо найти максимальную сумму элементов прямоугольного подмассива по всем возможным...

Динамическое программирование! - C++
#include &lt;cstdio&gt; #include &lt;algorithm&gt; using namespace std; int a, n, m; int main() { scanf(&quot; %d %d&quot;, &amp;n,...

Динамическое программирование - C++
Столкнулся с такой задачей. Есть 6 фигурок площадью 3. Нужно узнать, сколькими способами можно полностью замостить ими поле n на m,...

Динамическое программирование - C++
Помогите пожалуйста,кто может, со следующими задачами, так как в С++ слабо разбираюсь, а к понедельнику надо сдать... 1. Определить...

Динамическое программирование - C++
Ограничение по времени: 2 секунды Ограничение по памяти: 256 мегабайт У Пети есть полоска бумаги, разделенная на N клеток. Он хочет...

Динамическое программирование - C++
На расстоянии n шагов от магазина стоит А. Каждую минуту он выбирает куда сделать шаг: к магазину или в противоположном направлении. ...

0
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
11.07.2015, 22:43
Привет! Вот еще темы с ответами:

Динамическое программирование - C++
народ помогите пожалуйста. есть задача Написать программу, позволяющую вычислить количество чисел, не содержащих нули, сумма цифр...

Динамическое программирование. - C++
Помогите, пожалуйста, составить алгоритм по одному из ниже представленных заданий, используя методы динамического программирования и жадных...

ДП Динамическое программирование - C++
ограничение времени на тест: 0.5 сек. ограничение памяти на тест: 65536 KB. Рассмотрим все строки длины N, состоящие только из букв...

Динамическое программирование - C++
Помогите решить задачу! Я что-то особо не соображу... 1.Написать программу, реализующую действия: а. сформировать ленточную матрицу...


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

Или воспользуйтесь поиском по форуму:
1
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2018, vBulletin Solutions, Inc.
Рейтинг@Mail.ru