The relation among all the problems in the NP is a very important factor to find the way to solve the ancient problem "is P = NP?" In the nexts posts I'm going to analyze all the factors of the problems that I have studied to try to solve them. This post is only a small introduction to my first experience.
It is common that the NP-hard problems could be expressed with natural numbers, we do not need the real ones to abstract them. For example: It is well known that SAT problem works with boolean expressions (discret variables). We use 1 or 0 and the operations between this two numbers. The rucksack problem could be expressed only with the natural numbers.
The rucksack problem. I tried to solve this problem, but I realized that the fact of his combinationality made it difficult to solve with a good time with a polynomical cost. In some opportunities I have made algorithms for class or contests. I remember when I was in the Google's Hashcode and they gave us the pizza's issue. I thought that it was the same kind of problem, they put an NP-hard problem to see the algorithms, and the way we think.
The rucksack problem has a very simple way to solve it. The recursive algorithm which tests the combinations and if it fails it goes back and check other solution, at the end it gives you the best solution. the cost ... exponential, it has all the combinations.
I thought that I could develop a function to solve the problem. In the function the input is only the weight and the price of the book. In my first attempt I thoght that with one ponderation will work fine ... I was mistaken
I put an example: the max weight is 30kgm and the books are: [(30,45), (15,35), (15,35)] -> there are 3 books the x are the wight and the and are the price
The function divides the price out of the weight. Whit this operation I get a value to order the books. The most expensive ones usually go first than the others but not allways, the weight is important too.
The book (45/30) got more score than (25/30), but the book (1/1) got more score than 50/100. It is simple.
Then my algorithm is going to do this: "OK, let me see, I have this (45/30, 23/15, 24/15) ... The solution is: the last two books." I got the max score ... good, then I have to try with this same rucksack's weight and with other books: (45/30, 30/16, 35/16), and my algorithm said: "OK Carlos, I have your solution: the last book ... ". That was horrible, it was a bad solution, and I thought: "Okay I have to use the max weight too in the function" and I made other that worked for the second example but not for the first one.
And that was the beggining, the algorithm each day is bigger and better, the methods involved in it are more complex and have diffrent cases, but I need a function to solve the problem, and it probably does not exist.
Top comments (0)