Форум программистов, компьютерный форум, киберфорум
Алгоритмы
Войти
Регистрация
Восстановить пароль
Блоги Сообщество Поиск Заказать работу  
 
Рейтинг 4.57/7: Рейтинг темы: голосов - 7, средняя оценка - 4.57
5 / 5 / 2
Регистрация: 30.01.2012
Сообщений: 153

Динамическое программирование. Кааак?

03.12.2013, 18:30. Показов 1536. Ответов 4
Метки нет (Все метки)

Студворк — интернет-сервис помощи студентам
Здравствуйте.

Подскажите пожалуйста, в каком направлении двигаться для решения нижеизложенной задачи с помощью метода динамического программирования.
задача: Дано номер задачи, время необходимое на ее выполнение, баллы за ее выполнение и вероятность того, что студент ее решит. Дано также время теста. Нужно найти минимальное время выполнения теста, чтобы количество набранных баллов было максимальным.
0
Programming
Эксперт
39485 / 9562 / 3019
Регистрация: 12.04.2006
Сообщений: 41,671
Блог
03.12.2013, 18:30
Ответы с готовыми решениями:

Динамическое программирование
Добрый вечер. Мне задали написать задачи на динамическое программирование, но нам ничего не объясняли, поэтому обращаюсь к профессионалам....

Динамическое программирование
Добрый день! Возникла проблема в решении задач динамическим программированием Задача представлена в виде системы И для её решения...

Динамическое программирование
Есть задача: Необходимо подсчитать кол-во вариантов и вывести их для сдачи для некой суммы от 1 к ... до 10 р монетами достоинством...

4
Эксперт функциональных языков программированияЭксперт по математике/физике
4313 / 2105 / 431
Регистрация: 19.07.2009
Сообщений: 3,204
Записей в блоге: 24
03.12.2013, 21:55
гуглите задачу о рюкзаке.
0
5 / 5 / 2
Регистрация: 30.01.2012
Сообщений: 153
03.12.2013, 23:39  [ТС]
скажите а что значит ans.push (k) в данном алгоритме?
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
Сначала генерируем A.
for i = 0..W
  A[0][i] = 0;
for i = 0..N
  A[i][0] = 0;   //Первые элементы приравниваем к 0
for k = 1..N               
  for s = 0..W   //Перебираем для каждого k все вместисмости 
    if s >= w[k]    //Если текущий предмет вмещается в рюкзак
      A[k][s] = max(A[k-1][s], A[k-1][s-w[k]]+p[k]); //выбираем класть его или нет
    else 
      A[k][s] = A[k-1][s];             //иначе, не кладем
Затем найдем набор ans предметов, входящих в рюкзак, рекурсивной функцией:
findAns(k, s)
  if A[k][s] == 0 
    return;
  if A[k-1][s] == A[k][s]
    findAns(k-1, s);
  else 
    findAns(k-1, s - w[k]);
    ans.push(k);
0
294 / 265 / 48
Регистрация: 09.04.2013
Сообщений: 1,038
04.12.2013, 09:28
Цитата Сообщение от olea Посмотреть сообщение
скажите а что значит ans.push (k) в данном алгоритме?
Если вы брали код отсюда
http://neerc.ifmo.ru/wiki/inde... аке‎
То ans.push означает что данный предмет нам нужно взять в рюкзак
0
5 / 5 / 2
Регистрация: 30.01.2012
Сообщений: 153
05.12.2013, 00:49  [ТС]
Подскажите пожалуйста, в чем ошиблась

у меня массив структур с данными о номере
C++
1
2
3
4
5
struct Nomer{
    int Punctaj;
    int Vremea;
    int Veroeatnosti;
} Examen[NM];
переделанный алгоритм
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
    int k,s;
    for(i=0; i<W;i++)
        A[0][i] = 0;
    for(i=0; i<=n;i++)
        A[0][i] = 0;
    for(k=1; k<=n;k++)
        for(s=0; s<=W;s++)
            if (s >= Examen[k].Vremea)
                A[k][s] = max (A[k-1][s], A[k-1][s-Examen[k].Vremea]+Examen[k].Punctaj);
            else 
                A[k][s] = A[k-1][s];
 
    printf("%d ",  A[n][W]); // Хочу вывести и посмотреть максимальный балл - выводит 0
    findAns(n, W);
    getch();
}
 
int findAns(int k, int s){
    if (A[k][s] == 0 )
        return 0;
    if (A[k-1][s] == A[k][s])
        findAns(k-1, s);
    else {
        findAns(k-1, s - Examen[k].Vremea);
        printf("%d ",  Examen[k].Vremea);
    }   
}
0
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
inter-admin
Эксперт
29715 / 6470 / 2152
Регистрация: 06.03.2009
Сообщений: 28,500
Блог
05.12.2013, 00:49
Помогаю со студенческими работами здесь

Динамическое программирование
На шахматной доске 8 × 8 клеток произвольным образом расставлены шахматные фигуры. Необходимо для указанной фигуры (задаются координаты...

Динамическое программирование
Нужно составить рекурентную формулу для нахождения значения последней вершины Дан ломаная, состоящая из n вершин (3 ≤ n ≤ 50). Для...

Динамическое программирование
гайс, помогите пожалуйста есть одномерный массив длинной N мы можем ходить по массиву с шагом от I до J(только вперёд офк), скажем...

Динамическое программирование
Приветствую, форумчане. Так уж вышло, что жизнь свела меня с динамическим программированием. Есть задача: Стрелок стреляет по мишеням....

Динамическое программирование (задача)
Помогите советом. Есть задача: В арифметическом выражении разрешается использовать число 1, операции сложения, умножения и скобки. Какое...


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

Или воспользуйтесь поиском по форуму:
5
Ответ Создать тему
Новые блоги и статьи
Использование SDL3-callbacks вместо функции main() на Android, Desktop и WebAssembly
8Observer8 24.01.2026
Если вы откроете примеры для начинающих на официальном репозитории SDL3 в папке: examples, то вы увидите, что все примеры используют следующие четыре обязательные функции, а привычная функция main(). . .
моя боль
iceja 24.01.2026
Выложила интерполяцию кубическими сплайнами www. iceja. net REST сервисы временно не работают, только через Web. Написала за 56 рабочих часов этот сайт с нуля. При помощи perplexity. ai PRO , при. . .
Модель сукцессии микоризы
anaschu 24.01.2026
Решили писать научную статью с неким РОманом
http://iceja.net/ математические сервисы
iceja 20.01.2026
Обновила свой сайт http:/ / iceja. net/ , приделала Fast Fourier Transform экстраполяцию сигналов. Однако предсказывает далеко не каждый сигнал (см ограничения http:/ / iceja. net/ fourier/ docs ). Также. . .
http://iceja.net/ сервер решения полиномов
iceja 18.01.2026
Выкатила http:/ / iceja. net/ сервер решения полиномов (находит действительные корни полиномов методом Штурма). На сайте документация по API, но скажу прямо VPS слабенький и 200 000 полиномов. . .
Расчёт переходных процессов в цепи постоянного тока
igorrr37 16.01.2026
/ * Дана цепь(не выше 3-го порядка) постоянного тока с элементами R, L, C, k(ключ), U, E, J. Программа находит переходные токи и напряжения на элементах схемы классическим методом(1 и 2 з-ны. . .
Восстановить юзерскрипты Greasemonkey из бэкапа браузера
damix 15.01.2026
Если восстановить из бэкапа профиль Firefox после переустановки винды, то список юзерскриптов в Greasemonkey будет пустым. Но восстановить их можно так. Для этого понадобится консольная утилита. . .
Сукцессия микоризы: основная теория в виде двух уравнений.
anaschu 11.01.2026
https:/ / rutube. ru/ video/ 7a537f578d808e67a3c6fd818a44a5c4/
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin
Copyright ©2000 - 2026, CyberForum.ru