Here's the problem statement:
I have m chocolate bars, of integer length, and n children who want integer amounts of chocolate. Where the total chocolate needs of the children are less than or equal to the total amount of chocolate you have. You need to write an algorithm that distributes chocolate to the children by making the least number of cuts to the bars.
For example, for M = {1,3,7}, N = {1,3,4}, the least number of cuts would be 1.
I don't have any formal experience with algorithms, could anyone give me any hints on what I should start reading to tackle this problem in an efficient way?
This task can be reduced to solving several knapsack problems. To solve them, the principle of greedy search is usually used, and the number of cuts is the criterion of the search.
The first obvious step of the algorithm is checking the balance. The second step is to arrange the arrays of bars and chocolate needs, which will simplify further calculations. This implements the principle of greedy search. The third obvious step is to find and use all the bars, the sizes of which coincide with the needs.
The next step is to find and use all combinations of the bars what satisfy the needs. This task requires a "greedy" search in descending order of needs, which continues in the further calculations. This criterion is not optimal, but it allows to form a basic solution.
If not all the children have received chocolate, then the cuts become obvious. The search should be done according to the descending sizes of the tiles. First, one should check all possibilities to give the cut tiles to two children at once, then the same, but if one existing tile is used, etc. After that there is an obvious variant "one cut - one need", allowing to form the base variant. But if there remain computational resources, they can be used first to calculate the options of the type "two slits - three needs", etc.
Further optimization consists in returning back to the steps and calculation for the following variants.