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)
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.Example
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 (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.
- python - on the "c-proportion 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
- 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
- xcode - pod install [!] no `podfile 'found in the project directory
- vuejs - [vuetify] unable to locate target [data-app] 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