Currently, we are dealing with the business system we are designing, and there are fabrics wound in several meters.
We are struggling with the algorithm of how to make it the cheapest combination with the required length and number.
I'm investigating the knapsack problem and the greedy method, but I can't apply it to this pattern.

The fabric has the following characteristics.
Number of rolls per roll: 12m roll 30m roll (This is an example because it varies depending on the fabric)
Each cost
12m roll 8,000 yen
30m roll 19,000 yen
* Units with a larger number of turns are cheaper.

For example, if a customer orders 20 pieces of 5.5m long fabric,
If i cut a 12m roll of fabric by 5.5m in length, the number of sheets that can be created is two, leaving a 0.5m edge fabric.
If i cut a 30m roll of fabric by 5.5m in length, you can create 5 sheets and a 2.5m end fabric.

This is a formula that dynamically calculates the best combination of turns that will make the most money out of the above.


For example, here are some examples.

If i need 5 pieces of 5m length
Pattern (1) Rolling up to 12m requires 3 rolls, 8,000 yen x 3 rolls = 24,000 yen
Pattern 2: Rolling up to 30m requires 1 roll, 19,000 yen x 1 roll = 19,000 yen

In this case, the correct answer is to purchase one roll of 30m roll of Pattern ②.

If i need 7 pieces of 5m length
Pattern ① If only 12m is covered, 4 rolls are required, 8,000 yen x 4 rolls = 32,000 yen
Pattern ② If only 30m roll is covered, 2 rolls are required, 19,000 yen x 2 rolls = 38,000 yen
Pattern ③ 30m roll and 12m roll, 30m roll 1 roll, 12m roll 1 roll = 8,000 yen + 19,000 yen = 27,000 yen

In this case, the combination of 30m and 12m of pattern ③ is the cheapest.

What is the best way to calculate such dynamic and optimal patterns?
Please lend me your wisdom.

  • Answer # 1

    The number of turns is not limited to two, so it is generalized as follows.

    A customer orders N pieces of T-meter fabric.

    There are K types of turns, each L [i] meter C [i] circle. (I = 0 to K-1)

    If you simply discard the edge fabric, you can think of it as one roll and you can simplify it a little.

    There are K types of windings, each M [i] pieces C [i] yen.

    Writing a process to calculate the lowest price using dynamic programming is as follows.

    Calculate bottom price A [i] for 1 to N from 1 to N

    A [0] = 0 (i<0 also assumes A [i] = 0)

    A [i] = min (A [i-M [j]] + C [j]) for each kind of turns j

    The calculation amount is O (N * K).

    I only want the lowest price, but I think that I need information on what number of roles, so save it in A [i] with some structure.


    Given the following parameters:

    If customer orders 20 pieces of 5.5m long

    12m roll (2 sheets) 8,000 yen

    30m roll (5 sheets) 19,000 yen

    The lowest price for taking 20 is either of the following:

    18 lows + 8000

    15 low price + 19000

    You will feel like doing this operation from 1 to N from the bottom up.