Member 13540856 Ответов: 2

Помощь в линейном программировании

Привет,

У меня есть проблема, которую я не могу решить. Это похоже на то, как змея движется от вершины пирамиды к основанию и съедает лучший результат.

3
7 4
2 4 6
8 5 9 3

3+7+4+9=23


Но я не могу найти последних условий, которые обязывают выбирать числовые смежности вместо максимума строки.


Спасибо, что помог мне !

Что я уже пробовал:

Я уже писал об этом : 

CODE: SELECT ALL 
int n = ...; 
range rows = 1..n; 
int c[rows][rows] = ...; 
dvar boolean x[rows][rows]; 

maximize 

sum (i in rows, j in rows) c[i][j]*x[i][j] ; 



subject to { 
forall(i in rows) 
sum(j in rows) x[i][j]==1; 
}

George Jonsson

Не могли бы вы подробнее рассказать о проблеме, которую вы пытаетесь решить, поскольку она не является кристально ясной.
Разве не так должно быть "3+7+6+9=25", если вы хотите получить самый высокий балл в каждом ряду?

Member 13540856

Нет, потому что вы достигаете только смежности. Так что в третьей строке вы можете достичь только 2 или 4...

2 Ответов

Рейтинг:
2

Patrice T

Цитата:
Это похоже на то, как змея движется от вершины пирамиды к основанию и съедает лучший результат.

У вас нет волшебного способа узнать, является ли ответ лучшим или нет.
Это нападение с применением грубой силы.
Чтобы знать, что ответ-это лучший результат, вам нужно проверить все остальные ответы.
Вы должны построить алгоритм, который будет проверять каждое отдельное решение.

[Обновление]
Цитата:
Это в динамическое программирование... Но я ищу ограничение, чтобы избежать того, чтобы всегда брать лучший результат и брать только соседние лучшие результаты.

Как программист, ваша задача-создавать алгоритмы это решает конкретные проблемы, и вы не можете полагаться на кого-то другого, чтобы вечно делать это за вас, поэтому есть время, когда вам придется научиться этому. И чем скорее, тем лучше.
Когда вы просто просите решение, это похоже на попытку научиться водить машину, обучая кого-то другого.
Создание алгоритма - это в основном поиск математики и необходимая адаптация к вашей реальной проблеме.

Member 13540856

Это в динамическое программирование... Но я ищу ограничение, чтобы избежать того, чтобы всегда брать лучший результат и брать только соседние лучшие результаты.

Patrice T

"линейное программирование" и "динамическое программирование" - это две разные вещи

Member 13540856

Ah bon comme si je ne savais pas !

Patrice T

Данс Ле титре под названием c'est Ипе выбрал Эт данс Ле commentaire, се autrechose. Il faut choisir le sujet de la question au départ.
Paece que le problème est que la programmation lin"aire est sams repprt avec la problème à résoudre.

Patrice T

Et comment on devine puisque ti donnes le mauvais renseignement?

Member 13540856

УДАЛИТЬ ЭТОТ ПОСТ

Rick York

Я согласен - я думаю, что грубая сила была бы лучшим способом решить эту проблему. Есть много способов сделать это. Один из способов-в каждой точке принятия решения составить список возможностей, а затем пройти по списку, продолжая составлять списки в DPs. Это можно было бы сделать рекурсивно, но в этом нет необходимости. Есть способы имитировать рекурсию, не делая этого на самом деле, что полезно в среде с ограниченным стеком.

Рейтинг:
11

Member 13540856

Может ли кто-нибудь удалить этот пост ?