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.
ExampleFor 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
Related articles
 python  on the "cproportion number series" of the 3rd algorithm skill test
 [swift/ios] want to set the number of tabs dynamically with uitabbar
 algorithm for calculating the total number
 Simple implementation of Huffman algorithm for Java optimal binary tree
 C ++ implementation of large number multiplication algorithm
 JS algorithm to find the index position of a number in an array
 Java algorithm to adjust the order of the array so that the odd number is before the even number
 PHP implementation of statistical binary number algorithm example 1
 Python algorithm to find the number of different binary trees of n nodes
 Detailed examples of dynamically counting the number of bytes and characters of the current input
 Example of a PHP algorithm to find out the number of occurrences in an array that exceeds half the length of the array
 Java random number production algorithm example
 Java random number algorithm principle and implementation examples
 Javascript black hole number operation route finding algorithm (recursive algorithm) example
 Dynamically create tables and increase the number of table rows based on JavaScript
 Example of large number multiplication algorithm implemented in C ++
 python 3x  typeerror: 'method' object is not subscriptable
 python  you may need to restart the kernel to use updated packages error
 javascript  how to check if an element exists in puppeteer
 xcode  pod install [!] no `podfile 'found in the project directory
 vuejs  [vuetify] unable to locate target [dataapp] i want to unit test to avoid warning
 android studio  emulator: dsound: could not initialize about the error message directsoundcapture
 android studio  unresolved reference comes out in kotlin
 mysql startup failed [error] innodb: the innodb_system data file 'ibdata1' must be writable
 django  oserror: [winerror 123] the file name, directory name, or volume label syntax is incorrect : '<frozen importlib_boot
 python  importerror: cannot import name md5 error cannot be resolved
The number of turns is not limited to two, so it is generalized as follows.
A customer orders N pieces of Tmeter fabric.
There are K types of turns, each L [i] meter C [i] circle. (I = 0 to K1)
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 [iM [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.
Example:
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.