Help linear programming

Question

0.00/5 (No votes)

See more: (untagged)

Hello,

I have a problem that I can't solve. It's like a snake moving from the top to the pyramid to the bottom and eat the best score.

3
7 4
2 4 6
8 5 9 3

3+7+4+9=23

But I can't find the last conditions that oblige to choose number adjacents instead of the maximum of the line.

Thanks for helping me !

What I have tried:

I already wrote this :

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; 
}

Posted 25-Nov-17 4:18am

Member 13540856

Updated 25-Nov-17 7:50am

Add a Solution

Comments

George Jonsson 25-Nov-17 10:54am

Can you elaborate a little bit more about the problem you are trying to solve, as it is not crystal clear.
Shouldn't it be "3+7+6+9=25", if you want the highest score in each row?

Member 13540856 25-Nov-17 12:48pm

No because you only reach adjacents. So in the third line, you can only reach 2 or 4...

2 solutions

Solution 1

Quote:
It's like a snake moving from the top to the pyramid to the bottom and eat the best score.

You have no magic way to know that an answer is the best or not.
It is a brut force attack.
To know that an answer is best score, you need to check all other answers.
You have to build an algorithm that will check every single solution.

[Update]

Quote:
This is in dynamic programmation... But i search for a constraint to avoid to always take the best score and only take adjacent best scores.

As programmer, your job is to create algorithms that solve specific problems and you can't rely on someone else to eternally do it for you, so there is a time where you will have to learn how to. And the sooner, the better.
When you just ask for the solution, it is like trying to learn to drive a car by having someone else training.
Creating an algorithm is basically finding the maths and make necessary adaptation to fit your actual problem.

Posted 25-Nov-17 6:30am

Patrice T

Updated 25-Nov-17 7:03am

v2

Comments

Member 13540856 25-Nov-17 12:50pm

This is in dynamic programmation... But i search for a constraint to avoid to always take the best score and only take adjacent best scores.

Patrice T 25-Nov-17 12:57pm

'linear programming' and 'dynamic programmation' are 2 different things

Member 13540856 25-Nov-17 13:55pm

Ah bon comme si je ne savais pas !

Patrice T 25-Nov-17 14:02pm

Dans le titre c'est une chose et dans le commentaire, c'est 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 25-Nov-17 14:06pm

Et comment on devine puisque ti donnes le mauvais renseignement?

Member 13540856 25-Nov-17 13:57pm

DELETE THIS POST

Rick York 25-Nov-17 13:07pm

I agree - I think brute force would be the best way to solve it. There are many ways to go about it. One way is at every decision point, make a list of possibilities and then traverse the list, continuing making lists at DPs. It could be done recursively but that is not necessary. There are ways to mimic recursion without actually doing it which is useful in a stack-limited environment.

Add a Solution

Add your solution here

Treat my content as plain text, not as HTML

Preview 0

…

Existing Members

Sign in to your account

...or Join us

Download, Vote, Comment, Publish.

Your Email
Password
Forgot your password?

Your Email
This email is in use. Do you need your password?
Optional Password

I have read and agree to the Terms of Service and Privacy Policy
Please subscribe me to the CodeProject newsletters

When answering a question please:

Read the question carefully.
Understand that English isn't everyone's first language so be lenient of bad spelling and grammar.
If a question is poorly phrased then either ask for clarification, ignore it, or edit the question and fix the problem. Insults are not welcome.
Don't tell someone to read the manual. Chances are they have and don't get it. Provide an answer or move on to the next question.

Let's work to help developers, not make them feel stupid.

This content, along with any associated source code and files, is licensed under The Code Project Open License (CPOL)

Member 13540856 · Accepted Answer · 2017-11-25T07:50:00

Solution 2

Could someone delete this post ?

Posted 25-Nov-17 7:50am

Member 13540856