Форум программистов, компьютерный форум, киберфорум
Наши страницы
Алгоритмы
Войти
Регистрация
Восстановить пароль
 
Рейтинг 4.50/4: Рейтинг темы: голосов - 4, средняя оценка - 4.50
jlw
6 / 6 / 0
Регистрация: 30.09.2010
Сообщений: 18
1

Динамический метод решения

18.10.2010, 16:21. Просмотров 835. Ответов 6
Метки нет (Все метки)

Всем привет! Что-то никак не соображу, как решить 2 задачи методом динамического программирования.
Задачи очень сходны и поняв, как решается одна из них, думаю, со второй проблем не будет.

Задача 1

Даны N (2 ≤ N ≤ 24) целых чисел X1, X2, ..., XN (0 ≤ Xi ≤ 50 000 000). Расставить между ними знаки "+" и "-" так, чтобы значение получившегося выражения было равно заданному целому S (-1 000 000 000 ≤ S ≤ 1 000 000 000).

Задача 2

Имеется мешок картошки, состоящий из N (2 ≤ N ≤ 90) картофелин. Распределить их между двумя людьми так, чтобы разница была минимальной.
0
QA
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
18.10.2010, 16:21
Ответы с готовыми решениями:

Помогите определить тип задачи и метод решения
Здравствуйте уважаемые. По долгу службы решал недавно одну задачу (выбор комбинации и количества...

Как работает метод ОПГ надстройки "Поиск решения" Excel
Как работает метод ОПГ ("Метод обобщенного градиента") надстройки "Поиск решения" Excel? Есть ли...

Написать три алгоритма решения СЛАУ: Метод прогонки, метод квадратных корней, метод вращений
Начал писать курсовую. Нужно написать три алгоритма решения СЛАУ: прогонки, квадратных корней,...

Исследовать итерационный метод- метод касательных для решения нелинейных уравнений
прочитал много всего , но сам пример реализовать никак не могу , кто может помогите F(x) =...

Метод Ньютона (Метод касательных) для решения нелинейных уравнений
Преподаватель дал задание: Реализовать метод ньютона для решения нелинейных уравнений. Пробежался...

6
Norby
66 / 66 / 5
Регистрация: 12.03.2008
Сообщений: 392
19.10.2010, 07:56 2
По первой задаче: А если составить дерево вида X1, от него ветки + и -, далее по каждой из них X2, потом снова ветки + и - и т.д. На каждом шаге по значению выражения отсекать поддеревья. Как-то так.
0
vasy02
12 / 12 / 8
Регистрация: 19.10.2010
Сообщений: 237
19.10.2010, 09:14 3
задача 2

Pascal
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
program l;
var
  x,y,z:integer;
begin
  read(x);
  y:=x mod 2;
  if y=1 then
  begin
    x:=x div 2;
    z:=x+1;
  end
  else
  begin
    x:=x div 2;
    z:=x;
  end;
  write(x,' ',z);
end.
ну чёт типо того наверно))
если сможешь можешь сжать
0
gGrn-7DA
мну довольно <(-__-)l
212 / 201 / 15
Регистрация: 17.01.2010
Сообщений: 2,462
Завершенные тесты: 1
19.10.2010, 18:10 4
vasy02, бред! Твой код делает совсем не то, что требует от него дискретное динамическое программирование на НП-полной задаче=) Если бы твой код делал то, что должен, так быстро, то ты бы нобелевку схлопатал=)

Добавлено через 1 минуту
Цитата Сообщение от Norby Посмотреть сообщение
По первой задаче: А если составить дерево вида X1, от него ветки + и -, далее по каждой из них X2, потом снова ветки + и - и т.д. На каждом шаге по значению выражения отсекать поддеревья. Как-то так.
и перед тем было бы не плохо упорядочить числа по убыванию, вроде бы..не помню уже, уж сколько времени прошло с момента изучения(пол года, не меньше=)
0
vasy02
12 / 12 / 8
Регистрация: 19.10.2010
Сообщений: 237
20.10.2010, 21:16 5
Цитата Сообщение от gGrn-7DA Посмотреть сообщение
vasy02, бред! Твой код делает совсем не то, что требует от него дискретное динамическое программирование на НП-полной задаче=) Если бы твой код делал то, что должен, так быстро, то ты бы нобелевку схлопатал=)
по задаче то ответил дан мешок кортошки с n кортофелинами поделить их между двумя людьми
например там 5 кортошки делим их на двоих получается по 2 каждому, ну и мне одна
0
gGrn-7DA
мну довольно <(-__-)l
212 / 201 / 15
Регистрация: 17.01.2010
Сообщений: 2,462
Завершенные тесты: 1
21.10.2010, 20:53 6
ну ты еще по божески делишь... а то был гусар он тушу гуся делил, так ему туша и досталась=)
0
vasy02
12 / 12 / 8
Регистрация: 19.10.2010
Сообщений: 237
21.10.2010, 21:08 7
этож я, вася про себя никогда не забудет
0
21.10.2010, 21:08
Answers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
21.10.2010, 21:08

Метод простых итераций и метод Зейделя для решения СЛАУ
1. Методом простых итераций и методом Зейделя решить СЛАУ вида Bx=с B=\begin{pmatrix}21 &amp; 3 &amp; 1...

Метод деления отрезка пополам для решения нелинейных уравнений (метод дихотомии)
Здравствуйте. Помогите пожалуйста дописать программу. Вот что вымучал, но на сдаче завалили, типо...

Метод простых итераций и метод Зейделя. Пример решения
Привет всем! Мне нужно придумать и решить систему нелинейных уравнений методом простых итераций и...


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

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

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