Minimize Conversion Cost

Question

I had the following problem, but I can not find a solution for it.

Statement:

There are N glasses. It is assumed that each glass has an infinite capacity. The amount of wine in each glass is a positive integer other than zero, where the unit is ml. A type 1 transfer is defined as the transfer of one ml from glass i to glass j. Type 2 movement is defined as dropping one ml from glass i. All type 1 movements have a cost of one. All moves of type 2 have a value of k. Given the initial amount of wine in each glass, we need to take some two steps so that the amount of wine in each glass is a prime number (or zero). Print the minimum cost for such a conversion.

How to solve this problem? Any ideas for a possible solution?

Answer 1

Here is a rough sketch of my idea:

Prime numbers are distributed as follows x / ln (x) .

Also use the borders on this page to find where the closest downtime is relative to the amount of wine in this glass.

Once you find these numbers, you can reduce the problem to a graph with edges that have costs, which represent values ​​for moving from one glass to another (your type 1). And the nodes will be the glasses themselves.

Here you are left with a graph problem, and you need to think about the minimum cost paths on this graph. Your goal is to find the path to the minimum cost, which will lead to a state where all points are prime numbers.

If there are glasses that prevent you from doing this, drink them (moving type 2), the wine is right for you :)

UPDATE

I will write here some of the real thoughts that we discussed in the chat:

• bilateral compliance has been mentioned and it is likely that the problem can be reduced to
• you can first get the main sections between every 2 points (the main sections of the sum of every 2 points), and these sections are edges in the graph. you also add edges for type 2 moves. You can tie the costs one way or another and then run the minimum flow algorithm to solve the problem.
• The problem may also be that you need all of the facets mentioned above, since the optimal solution may not imply the adoption of an optimal simple parity for each of the points

Answer 2

This type of problem is solvable by dynamic programming and is similar to calculating the minimum line editing distance that you can solve using the Hirschberg algorithm .

There are actually two stages. First you need to find combinations of candidates, then calculate the minimum editing distance for each of these candidates. The answer with the smallest editing distance is the answer.

For example, suppose you have totals, such as 16 14 8. In the first step, you need to list each possible combination: {37 0 0} {31 7 0}, etc. Then you use the Hirschberg algorithm to calculate the minimum editing distance for each of these candidates.