teratail
回答率
85.47%
質問するログイン新規登録
トップアルゴリズムに関する質問最適な組み合わせの巻数を動的に算出するアルゴリズム

編集履歴

回答編集履歴

15

金額修正

2018/08/29 09:02

投稿

set0gut1
set0gut1

スコア2413

test CHANGED
@@ -48,7 +48,7 @@
48
48
 
49
49
  - 12m巻（2枚） 8,000円
50
50
 
51
- - 30m巻（5枚） 22,000円
51
+ - 30m巻（5枚） 19,000円
52
52
 
53
53
 
54
54
 
@@ -58,7 +58,7 @@
58
58
 
59
59
  - 18枚の最安値 + 8000
60
60
 
61
- - 15枚の最安値 + 22000
61
+ - 15枚の最安値 + 19000
62
62
 
63
63
 
64
64
 

14

推敲

2018/08/29 09:01

投稿

set0gut1
set0gut1

スコア2413

test CHANGED
@@ -24,7 +24,7 @@
24
24
 
25
25
  - A[0] = 0 （i < 0 のときも A[i] = 0 とみなす）
26
26
 
27
- - A[i] = min( 巻数の各種類 j に対して A[i-M[j]] + C[j])
27
+ - A[i] = min( 巻数の各種類 j に対して A[i-M[j]] + C[j] )
28
28
 
29
29
 
30
30
 

13

推敲

2018/08/29 06:01

投稿

set0gut1
set0gut1

スコア2413

test CHANGED
@@ -32,7 +32,7 @@
32
32
 
33
33
 
34
34
 
35
- 最安値しか求めてないですが、どのロールを何枚っていう情報も要ると思うので、適宜構造体かなにかで A[i] に保存してください。
35
+ 最安値しか求めてないですが、どのロールを何個っていう情報も要ると思うので、適宜構造体かなにかで A[i] に保存してください。
36
36
 
37
37
 
38
38
 

12

アルゴリズム改善

2018/08/29 05:55

投稿

set0gut1
set0gut1

スコア2413

test CHANGED
@@ -24,11 +24,11 @@
24
24
 
25
25
  - A[0] = 0 （i < 0 のときも A[i] = 0 とみなす）
26
26
 
27
- - A[i] = min( 巻数の各種類 j に対して min( A[i-M[j]] + C[j] 〜 A[i-1] + C[j] ))
27
+ - A[i] = min( 巻数の各種類 j に対して A[i-M[j]] + C[j])
28
28
 
29
29
 
30
30
 
31
- 計算量は、1ロールで何枚取れるかの最大値を仮に x と置くと O(N*K*x) となります。
31
+ 計算量は O(N*K) となります。
32
32
 
33
33
 
34
34
 
@@ -58,17 +58,7 @@
58
58
 
59
59
  - 18枚の最安値 + 8000
60
60
 
61
- - 19枚の最安値 + 8000
62
-
63
61
  - 15枚の最安値 + 22000
64
-
65
- - 16枚の最安値 + 22000
66
-
67
- - 17枚の最安値 + 22000
68
-
69
- - 18枚の最安値 + 22000
70
-
71
- - 19枚の最安値 + 22000
72
62
 
73
63
 
74
64
 

11

推敲

2018/08/29 05:49

投稿

set0gut1
set0gut1

スコア2413

test CHANGED
@@ -20,11 +20,9 @@
20
20
 
21
21
 
22
22
 
23
- - i 枚とるための最安値 A[i] を計算する
23
+ - i 枚とるための最安値 A[i] を 1〜N にかけてボトムアップで計算する
24
24
 
25
- - A[0] = 0
26
-
27
- - i < 0 のときも A[i] = 0 とみなす
25
+ - A[0] = 0 （i < 0 のときも A[i] = 0 とみなす）
28
26
 
29
27
  - A[i] = min( 巻数の各種類 j に対して min( A[i-M[j]] + C[j] 〜 A[i-1] + C[j] ))
30
28
 

10

推敲

2018/08/29 04:50

投稿

set0gut1
set0gut1

スコア2413

test CHANGED
@@ -8,11 +8,11 @@
8
8
 
9
9
 
10
10
 
11
- 端生地は単純に捨てるとすると、巻数の種類がちょっと単純化できます。
11
+ 端生地は単純に捨てるとすると、1ロール何枚と見なせて、ちょっと単純化できます。
12
12
 
13
13
 
14
14
 
15
- - 巻数の種類は K 種類存在し、それぞれ M[i] 枚 C[i] 円とする。（Mi = Li / T, 小数切り捨て）
15
+ - 巻数の種類は K 種類存在し、それぞれ M[i] 枚 C[i] 円とする。
16
16
 
17
17
 
18
18
 

9

計算量について追記

2018/08/29 04:32

投稿

set0gut1
set0gut1

スコア2413

test CHANGED
@@ -27,6 +27,10 @@
27
27
  - i < 0 のときも A[i] = 0 とみなす
28
28
 
29
29
  - A[i] = min( 巻数の各種類 j に対して min( A[i-M[j]] + C[j] 〜 A[i-1] + C[j] ))
30
+
31
+
32
+
33
+ 計算量は、1ロールで何枚取れるかの最大値を仮に x と置くと O(N*K*x) となります。
30
34
 
31
35
 
32
36
 

8

計算量についての記述消す

2018/08/29 04:20

投稿

set0gut1
set0gut1

スコア2413

test CHANGED
@@ -29,8 +29,6 @@
29
29
  - A[i] = min( 巻数の各種類 j に対して min( A[i-M[j]] + C[j] 〜 A[i-1] + C[j] ))
30
30
 
31
31
 
32
-
33
- 計算量は…よく分からないですけど O(T*N*K) より悪くはないです。
34
32
 
35
33
  最安値しか求めてないですが、どのロールを何枚っていう情報も要ると思うので、適宜構造体かなにかで A[i] に保存してください。
36
34
 

7

計算量修正

2018/08/29 04:15

投稿

set0gut1
set0gut1

スコア2413

test CHANGED
@@ -30,7 +30,7 @@
30
30
 
31
31
 
32
32
 
33
- 計算量は…よく分からないですけど O(T*T*K) より悪くはないです。
33
+ 計算量は…よく分からないですけど O(T*N*K) より悪くはないです。
34
34
 
35
35
  最安値しか求めてないですが、どのロールを何枚っていう情報も要ると思うので、適宜構造体かなにかで A[i] に保存してください。
36
36
 

6

計算量について追記

2018/08/29 04:14

投稿

set0gut1
set0gut1

スコア2413

test CHANGED
@@ -29,6 +29,8 @@
29
29
  - A[i] = min( 巻数の各種類 j に対して min( A[i-M[j]] + C[j] 〜 A[i-1] + C[j] ))
30
30
 
31
31
 
32
+
33
+ 計算量は…よく分からないですけど O(T*T*K) より悪くはないです。
32
34
 
33
35
  最安値しか求めてないですが、どのロールを何枚っていう情報も要ると思うので、適宜構造体かなにかで A[i] に保存してください。
34
36
 

5

推敲

2018/08/29 04:11

投稿

set0gut1
set0gut1

スコア2413

test CHANGED
@@ -26,7 +26,7 @@
26
26
 
27
27
  - i < 0 のときも A[i] = 0 とみなす
28
28
 
29
- - A[i] = min( 巻数の種類 j に対して A[i-M[j]] + C[j] 〜 A[i-1] + C[j] の最小値 )
29
+ - A[i] = min( 巻数の各種類 j に対して min( A[i-M[j]] + C[j] 〜 A[i-1] + C[j] ))
30
30
 
31
31
 
32
32
 

4

推敲

2018/08/29 04:09

投稿

set0gut1
set0gut1

スコア2413

test CHANGED
@@ -42,11 +42,11 @@
42
42
 
43
43
 
44
44
 
45
+ - お客様から長さ5.5mの生地を20枚ほしいと注文があった場合
46
+
45
47
  - 12m巻（2枚） 8,000円
46
48
 
47
49
  - 30m巻（5枚） 22,000円
48
-
49
- - お客様から長さ5.5mの生地を20枚ほしいと注文があった場合
50
50
 
51
51
 
52
52
 

3

微修正

2018/08/29 04:08

投稿

set0gut1
set0gut1

スコア2413

test CHANGED
@@ -31,10 +31,6 @@
31
31
 
32
32
 
33
33
  最安値しか求めてないですが、どのロールを何枚っていう情報も要ると思うので、適宜構造体かなにかで A[i] に保存してください。
34
-
35
-
36
-
37
- ------
38
34
 
39
35
 
40
36
 

2

例追加

2018/08/29 04:03

投稿

set0gut1
set0gut1

スコア2413

test CHANGED
@@ -31,3 +31,47 @@
31
31
 
32
32
 
33
33
  最安値しか求めてないですが、どのロールを何枚っていう情報も要ると思うので、適宜構造体かなにかで A[i] に保存してください。
34
+
35
+
36
+
37
+ ------
38
+
39
+
40
+
41
+ ■例:
42
+
43
+
44
+
45
+ 次のようなパラメータだとします。
46
+
47
+
48
+
49
+ - 12m巻（2枚） 8,000円
50
+
51
+ - 30m巻（5枚） 22,000円
52
+
53
+ - お客様から長さ5.5mの生地を20枚ほしいと注文があった場合
54
+
55
+
56
+
57
+ 20枚取るための最安値は次のいずれかで、
58
+
59
+
60
+
61
+ - 18枚の最安値 + 8000
62
+
63
+ - 19枚の最安値 + 8000
64
+
65
+ - 15枚の最安値 + 22000
66
+
67
+ - 16枚の最安値 + 22000
68
+
69
+ - 17枚の最安値 + 22000
70
+
71
+ - 18枚の最安値 + 22000
72
+
73
+ - 19枚の最安値 + 22000
74
+
75
+
76
+
77
+ この操作を 1 から N までボトムアップでやる感じになります。

1

枚数あまりのケースを考慮してなかったので修正します

2018/08/29 04:03

投稿

set0gut1
set0gut1

スコア2413

test CHANGED
@@ -26,10 +26,8 @@
26
26
 
27
27
  - i < 0 のときも A[i] = 0 とみなす
28
28
 
29
- - A[i] = min( 巻数の種類 j に対して A[i-M[j]] + C[j] の最小値 )
29
+ - A[i] = min( 巻数の種類 j に対して A[i-M[j]] + C[j] 〜 A[i-1] + C[j] の最小値 )
30
30
 
31
31
 
32
32
 
33
- 計算量としては「O(お客様からの要望の長さ) * O(巻数の種類)」となります。
34
-
35
33
  最安値しか求めてないですが、どのロールを何枚っていう情報も要ると思うので、適宜構造体かなにかで A[i] に保存してください。