回答編集履歴
15
金額修正
answer
CHANGED
|
@@ -23,11 +23,11 @@
|
|
|
23
23
|
|
|
24
24
|
- お客様から長さ5.5mの生地を20枚ほしいと注文があった場合
|
|
25
25
|
- 12m巻（2枚） 8,000円
|
|
26
|
-
- 30m巻（5枚）
|
|
26
|
+
- 30m巻（5枚） 19,000円
|
|
27
27
|
|
|
28
28
|
20枚取るための最安値は次のいずれかで、
|
|
29
29
|
|
|
30
30
|
- 18枚の最安値 + 8000
|
|
31
|
-
- 15枚の最安値 +
|
|
31
|
+
- 15枚の最安値 + 19000
|
|
32
32
|
|
|
33
33
|
この操作を 1 から N までボトムアップでやる感じになります。
|
14
推敲
answer
CHANGED
|
@@ -11,7 +11,7 @@
|
|
|
11
11
|
|
|
12
12
|
- i 枚とるための最安値 A[i] を 1〜N にかけてボトムアップで計算する
|
|
13
13
|
- A[0] = 0 （i < 0 のときも A[i] = 0 とみなす）
|
|
14
|
-
- A[i] = min( 巻数の各種類 j に対して A[i-M[j]] + C[j])
|
|
14
|
+
- A[i] = min( 巻数の各種類 j に対して A[i-M[j]] + C[j] )
|
|
15
15
|
|
|
16
16
|
計算量は O(N*K) となります。
|
|
17
17
|
|
13
推敲
answer
CHANGED
|
@@ -15,7 +15,7 @@
|
|
|
15
15
|
|
|
16
16
|
計算量は O(N*K) となります。
|
|
17
17
|
|
|
18
|
-
最安値しか求めてないですが、どのロールを何
|
|
18
|
+
最安値しか求めてないですが、どのロールを何個っていう情報も要ると思うので、適宜構造体かなにかで A[i] に保存してください。
|
|
19
19
|
|
|
20
20
|
■例:
|
|
21
21
|
|
12
アルゴリズム改善
answer
CHANGED
|
@@ -11,9 +11,9 @@
|
|
|
11
11
|
|
|
12
12
|
- i 枚とるための最安値 A[i] を 1〜N にかけてボトムアップで計算する
|
|
13
13
|
- A[0] = 0 （i < 0 のときも A[i] = 0 とみなす）
|
|
14
|
-
- A[i] = min( 巻数の各種類 j に対して
|
|
14
|
+
- A[i] = min( 巻数の各種類 j に対して A[i-M[j]] + C[j])
|
|
15
15
|
|
|
16
|
-
計算量は
|
|
16
|
+
計算量は O(N*K) となります。
|
|
17
17
|
|
|
18
18
|
最安値しか求めてないですが、どのロールを何枚っていう情報も要ると思うので、適宜構造体かなにかで A[i] に保存してください。
|
|
19
19
|
|
|
@@ -28,11 +28,6 @@
|
|
|
28
28
|
20枚取るための最安値は次のいずれかで、
|
|
29
29
|
|
|
30
30
|
- 18枚の最安値 + 8000
|
|
31
|
-
- 19枚の最安値 + 8000
|
|
32
31
|
- 15枚の最安値 + 22000
|
|
33
|
-
- 16枚の最安値 + 22000
|
|
34
|
-
- 17枚の最安値 + 22000
|
|
35
|
-
- 18枚の最安値 + 22000
|
|
36
|
-
- 19枚の最安値 + 22000
|
|
37
32
|
|
|
38
33
|
この操作を 1 から N までボトムアップでやる感じになります。
|
11
推敲
answer
CHANGED
|
@@ -9,9 +9,8 @@
|
|
|
9
9
|
|
|
10
10
|
動的計画法を用いて最安値を算出する処理を書くと、次のようになります。
|
|
11
11
|
|
|
12
|
-
- i 枚とるための最安値 A[i] を計算する
|
|
12
|
+
- i 枚とるための最安値 A[i] を 1〜N にかけてボトムアップで計算する
|
|
13
|
-
- A[0] = 0
|
|
14
|
-
- i < 0 のときも A[i] = 0 とみなす
|
|
13
|
+
- A[0] = 0 （i < 0 のときも A[i] = 0 とみなす）
|
|
15
14
|
- A[i] = min( 巻数の各種類 j に対して min( A[i-M[j]] + C[j] 〜 A[i-1] + C[j] ))
|
|
16
15
|
|
|
17
16
|
計算量は、1ロールで何枚取れるかの最大値を仮に x と置くと O(N*K*x) となります。
|
10
推敲
answer
CHANGED
|
@@ -3,9 +3,9 @@
|
|
|
3
3
|
- お客様から長さ T メートルの生地を N 枚ほしいと注文がある。
|
|
4
4
|
- 巻数の種類は K 種類存在し、それぞれ L[i] メートル C[i] 円とする。（i = 0 〜 K-1）
|
|
5
5
|
|
|
6
|
-
端生地は単純に捨てるとすると、
|
|
6
|
+
端生地は単純に捨てるとすると、1ロール何枚と見なせて、ちょっと単純化できます。
|
|
7
7
|
|
|
8
|
-
- 巻数の種類は K 種類存在し、それぞれ M[i] 枚 C[i] 円とする。
|
|
8
|
+
- 巻数の種類は K 種類存在し、それぞれ M[i] 枚 C[i] 円とする。
|
|
9
9
|
|
|
10
10
|
動的計画法を用いて最安値を算出する処理を書くと、次のようになります。
|
|
11
11
|
|
9
計算量について追記
answer
CHANGED
|
@@ -14,6 +14,8 @@
|
|
|
14
14
|
- i < 0 のときも A[i] = 0 とみなす
|
|
15
15
|
- A[i] = min( 巻数の各種類 j に対して min( A[i-M[j]] + C[j] 〜 A[i-1] + C[j] ))
|
|
16
16
|
|
|
17
|
+
計算量は、1ロールで何枚取れるかの最大値を仮に x と置くと O(N*K*x) となります。
|
|
18
|
+
|
|
17
19
|
最安値しか求めてないですが、どのロールを何枚っていう情報も要ると思うので、適宜構造体かなにかで A[i] に保存してください。
|
|
18
20
|
|
|
19
21
|
■例:
|
8
計算量についての記述消す
answer
CHANGED
|
@@ -14,7 +14,6 @@
|
|
|
14
14
|
- i < 0 のときも A[i] = 0 とみなす
|
|
15
15
|
- A[i] = min( 巻数の各種類 j に対して min( A[i-M[j]] + C[j] 〜 A[i-1] + C[j] ))
|
|
16
16
|
|
|
17
|
-
計算量は…よく分からないですけど O(T*N*K) より悪くはないです。
|
|
18
17
|
最安値しか求めてないですが、どのロールを何枚っていう情報も要ると思うので、適宜構造体かなにかで A[i] に保存してください。
|
|
19
18
|
|
|
20
19
|
■例:
|
7
計算量修正
answer
CHANGED
|
@@ -14,7 +14,7 @@
|
|
|
14
14
|
- i < 0 のときも A[i] = 0 とみなす
|
|
15
15
|
- A[i] = min( 巻数の各種類 j に対して min( A[i-M[j]] + C[j] 〜 A[i-1] + C[j] ))
|
|
16
16
|
|
|
17
|
-
計算量は…よく分からないですけど O(T*
|
|
17
|
+
計算量は…よく分からないですけど O(T*N*K) より悪くはないです。
|
|
18
18
|
最安値しか求めてないですが、どのロールを何枚っていう情報も要ると思うので、適宜構造体かなにかで A[i] に保存してください。
|
|
19
19
|
|
|
20
20
|
■例:
|
6
計算量について追記
answer
CHANGED
|
@@ -14,6 +14,7 @@
|
|
|
14
14
|
- i < 0 のときも A[i] = 0 とみなす
|
|
15
15
|
- A[i] = min( 巻数の各種類 j に対して min( A[i-M[j]] + C[j] 〜 A[i-1] + C[j] ))
|
|
16
16
|
|
|
17
|
+
計算量は…よく分からないですけど O(T*T*K) より悪くはないです。
|
|
17
18
|
最安値しか求めてないですが、どのロールを何枚っていう情報も要ると思うので、適宜構造体かなにかで A[i] に保存してください。
|
|
18
19
|
|
|
19
20
|
■例:
|
5
推敲
answer
CHANGED
|
@@ -12,7 +12,7 @@
|
|
|
12
12
|
- i 枚とるための最安値 A[i] を計算する
|
|
13
13
|
- A[0] = 0
|
|
14
14
|
- i < 0 のときも A[i] = 0 とみなす
|
|
15
|
-
- A[i] = min( 巻数の種類 j に対して A[i-M[j]] + C[j] 〜 A[i-1] + C[j]
|
|
15
|
+
- A[i] = min( 巻数の各種類 j に対して min( A[i-M[j]] + C[j] 〜 A[i-1] + C[j] ))
|
|
16
16
|
|
|
17
17
|
最安値しか求めてないですが、どのロールを何枚っていう情報も要ると思うので、適宜構造体かなにかで A[i] に保存してください。
|
|
18
18
|
|
4
推敲
answer
CHANGED
|
@@ -20,9 +20,9 @@
|
|
|
20
20
|
|
|
21
21
|
次のようなパラメータだとします。
|
|
22
22
|
|
|
23
|
+
- お客様から長さ5.5mの生地を20枚ほしいと注文があった場合
|
|
23
24
|
- 12m巻（2枚） 8,000円
|
|
24
25
|
- 30m巻（5枚） 22,000円
|
|
25
|
-
- お客様から長さ5.5mの生地を20枚ほしいと注文があった場合
|
|
26
26
|
|
|
27
27
|
20枚取るための最安値は次のいずれかで、
|
|
28
28
|
|
3
微修正
answer
CHANGED
|
@@ -16,8 +16,6 @@
|
|
|
16
16
|
|
|
17
17
|
最安値しか求めてないですが、どのロールを何枚っていう情報も要ると思うので、適宜構造体かなにかで A[i] に保存してください。
|
|
18
18
|
|
|
19
|
-
------
|
|
20
|
-
|
|
21
19
|
■例:
|
|
22
20
|
|
|
23
21
|
次のようなパラメータだとします。
|
2
例追加
answer
CHANGED
|
@@ -14,4 +14,26 @@
|
|
|
14
14
|
- i < 0 のときも A[i] = 0 とみなす
|
|
15
15
|
- A[i] = min( 巻数の種類 j に対して A[i-M[j]] + C[j] 〜 A[i-1] + C[j] の最小値 )
|
|
16
16
|
|
|
17
|
-
最安値しか求めてないですが、どのロールを何枚っていう情報も要ると思うので、適宜構造体かなにかで A[i] に保存してください。
|
|
17
|
+
最安値しか求めてないですが、どのロールを何枚っていう情報も要ると思うので、適宜構造体かなにかで A[i] に保存してください。
|
|
18
|
+
|
|
19
|
+
------
|
|
20
|
+
|
|
21
|
+
■例:
|
|
22
|
+
|
|
23
|
+
次のようなパラメータだとします。
|
|
24
|
+
|
|
25
|
+
- 12m巻（2枚） 8,000円
|
|
26
|
+
- 30m巻（5枚） 22,000円
|
|
27
|
+
- お客様から長さ5.5mの生地を20枚ほしいと注文があった場合
|
|
28
|
+
|
|
29
|
+
20枚取るための最安値は次のいずれかで、
|
|
30
|
+
|
|
31
|
+
- 18枚の最安値 + 8000
|
|
32
|
+
- 19枚の最安値 + 8000
|
|
33
|
+
- 15枚の最安値 + 22000
|
|
34
|
+
- 16枚の最安値 + 22000
|
|
35
|
+
- 17枚の最安値 + 22000
|
|
36
|
+
- 18枚の最安値 + 22000
|
|
37
|
+
- 19枚の最安値 + 22000
|
|
38
|
+
|
|
39
|
+
この操作を 1 から N までボトムアップでやる感じになります。
|
1
枚数あまりのケースを考慮してなかったので修正します
answer
CHANGED
|
@@ -12,7 +12,6 @@
|
|
|
12
12
|
- i 枚とるための最安値 A[i] を計算する
|
|
13
13
|
- A[0] = 0
|
|
14
14
|
- i < 0 のときも A[i] = 0 とみなす
|
|
15
|
-
- A[i] = min( 巻数の種類 j に対して A[i-M[j]] + C[j] の最小値 )
|
|
15
|
+
- A[i] = min( 巻数の種類 j に対して A[i-M[j]] + C[j] 〜 A[i-1] + C[j] の最小値 )
|
|
16
16
|
|
|
17
|
-
計算量としては「O(お客様からの要望の長さ) * O(巻数の種類)」となります。
|
|
18
17
|
最安値しか求めてないですが、どのロールを何枚っていう情報も要ると思うので、適宜構造体かなにかで A[i] に保存してください。
|