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

編集履歴

回答編集履歴

5

小数点対応、例題４パターン全て出力可能

2018/08/29 11:16

投稿

opyon
opyon

スコア1009

answer CHANGED
@@ -1,8 +1,7 @@
1
- 作り直しの途中ですが取り急ぎ更新します。
2
- 複数の組み合わせを実装しました。
1
+ 複数の組み合わせ及び小数点対応しました。
3
2
  出力結果はコード内のコメントに残してます。
4
- ※整数のみ対応
5
- ※小数点の長さは修正中
3
+ 例題全４パターン出力可能です。
4
+ //5x5//5x7//18x2//5.5x20
6
5
 
7
6
  ```java
8
7
 
@@ -38,6 +37,7 @@
38
37
  //5x5
39
38
  //5x7
40
39
  //18x2
40
+ //5.5x20
41
41
 
42
42
  // 5m x 5枚必要
43
43
  // 30m巻 x 1ロール = 19000円
@@ -52,9 +52,14 @@
52
52
  // 30m巻 x 2ロール = 38000円
53
53
  // 最安値総計38000円
54
54
 
55
+ // 5.5m x 20枚必要
56
+ // 12m巻 x 2ロール = 16000円
57
+ // 30m巻 x 3ロール = 57000円
58
+ // 最安値総計73000円
59
+
55
- int a = 18;
60
+ double a = 18;
56
61
  int b = 2;
57
- int c = a * b;
62
+ double c = a * b;
58
63
 
59
64
  int[] d = { 12, 30 };
60
65
  int[] e = { 8000, 19000 };
@@ -72,11 +77,10 @@
72
77
  System.out.println(" 最安値総計" + sum + "円");
73
78
  }
74
79
 
75
- static int[] func(int a, int b, int c, int[] d, int[] e) {
80
+ static int[] func(double a, int b, double c, int[] d, int[] e) {
76
81
 
77
82
  int n = d.length;
78
83
  int x;
79
- int sum;
80
84
  int[] result = new int[n];
81
85
  int[][] chk1 = new int[n][2];
82
86
 
@@ -91,11 +95,17 @@
91
95
  }
92
96
 
93
97
  //最安値単価の商品=fで端数が出るまでまかなう
94
- result[f] = c / d[f];
98
+ result[f] = (int) (c / ((d[f] / (int) a) * a));
95
99
 
96
100
  //残り長さを端数で更新
97
- c = c % d[f];
101
+ // c = c % d[f];
98
102
 
103
+ c -= result[f] * d[f];
104
+
105
+ if(c<0) {
106
+ return result;
107
+ }
108
+
99
109
  //d0 //d1
100
110
  //12 //30
101
111
  //a5 b5
@@ -110,7 +120,14 @@
110
120
  //12 //30
111
121
  //a18 b2
112
122
  //c36
123
+
124
+ //d0 //d1
125
+ //12 //30
126
+ //a5.5 b20
127
+ //c110.0
113
128
 
129
+ //30/5.5=5
130
+
114
131
  for (int i = 0; i < n; i++) {
115
132
 
116
133
  if (d[i] < a) {
@@ -121,7 +138,7 @@
121
138
  chk1[i][0] = 1;
122
139
  chk1[i][1] = e[i];
123
140
  } else {
124
- x = (int) Math.ceil(1.0 * b / (d[i] / a));
141
+ x = (int) Math.ceil(1.0 * c / d[i]);
125
142
  chk1[i][0] = x;
126
143
  chk1[i][1] = e[i] * x;
127
144
  }
@@ -146,6 +163,7 @@
146
163
  return result;
147
164
  }
148
165
  }
166
+
149
167
  ```
150
168
  ※以下初回分ですがコメント頂いているので残してます。
151
169
  ---

4

複数の組み合わせの場合に対応

2018/08/29 11:16

投稿

opyon
opyon

スコア1009

answer CHANGED
@@ -1,6 +1,8 @@
1
- 作り直しの途中ですが取り急ぎ時間がないので更新します。
1
+ 作り直しの途中ですが取り急ぎ更新します。
2
- 複数の組み合わせは未実装。
2
+ 複数の組み合わせを実装しました。
3
3
  出力結果はコード内のコメントに残してます。
4
+ ※整数のみ対応
5
+ ※小数点の長さは修正中
4
6
 
5
7
  ```java
6
8
 
@@ -42,8 +44,9 @@
42
44
  // 最安値総計19000円
43
45
 
44
46
  // 5m x 7枚必要
45
- // 12m巻 x 4ロール = 32000円
47
+ // 12m巻 x 1ロール = 8000円
48
+ // 30m巻 x 1ロール = 19000円
46
- // 最安値総計32000円
49
+ // 最安値総計27000円
47
50
 
48
51
  // 18m x 2枚必要
49
52
  // 30m巻 x 2ロール = 38000円
@@ -72,11 +75,27 @@
72
75
  static int[] func(int a, int b, int c, int[] d, int[] e) {
73
76
 
74
77
  int n = d.length;
78
+ int x;
79
+ int sum;
75
80
  int[] result = new int[n];
76
- int sum;
77
- int x;
78
81
  int[][] chk1 = new int[n][2];
79
82
 
83
+ //最安値単価の商品IDを取得=f
84
+ int f = 0;
85
+ for (int i = 0; i < d.length - 1; i++) {
86
+ if (e[i] / d[i] < e[i + 1] / d[i + 1]) {
87
+ f = i;
88
+ } else {
89
+ f = i + 1;
90
+ }
91
+ }
92
+
93
+ //最安値単価の商品=fで端数が出るまでまかなう
94
+ result[f] = c / d[f];
95
+
96
+ //残り長さを端数で更新
97
+ c = c % d[f];
98
+
80
99
  //d0 //d1
81
100
  //12 //30
82
101
  //a5 b5
@@ -86,7 +105,7 @@
86
105
  //12 //30
87
106
  //a5 b7
88
107
  //c35
89
-
108
+
90
109
  //d0 //d1
91
110
  //12 //30
92
111
  //a18 b2
@@ -123,7 +142,7 @@
123
142
  }
124
143
  }
125
144
 
126
- result[ans] = chk1[ans][0];
145
+ result[ans] += chk1[ans][0];
127
146
  return result;
128
147
  }
129
148
  }

3

初回分の文章を全てコード内に移動。

2018/08/29 10:33

投稿

opyon
opyon

スコア1009

answer CHANGED
@@ -128,11 +128,9 @@
128
128
  }
129
129
  }
130
130
  ```
131
-
132
-
133
131
  ※以下初回分ですがコメント頂いているので残してます。
134
132
  ---
135
-
133
+ ```java
136
134
  言語が何か分からないので自分の勉強のために例題としてjavaで実装してみました。
137
135
  if文とfor文くらいしか使ってないですが何かの参考になればと思います。
138
136
  5x5と5x7のケースしかテストしていません。
@@ -167,9 +165,6 @@
167
165
  12m巻 x 1ロール = 8000円
168
166
  総計30000円
169
167
 
170
- ```java
171
-
172
-
173
168
  public class memo102 {
174
169
 
175
170
  // 長さ5mを５枚必要な場合

2

最初から作り直しました。

2018/08/29 08:55

投稿

opyon
opyon

スコア1009

answer CHANGED
@@ -1,3 +1,138 @@
1
+ 作り直しの途中ですが取り急ぎ時間がないので更新します。
2
+ 複数の組み合わせは未実装。
3
+ 出力結果はコード内のコメントに残してます。
4
+
5
+ ```java
6
+
7
+ public class memo102 {
8
+
9
+ // 例えば、いくつか例です。
10
+ //
11
+ // 長さ5mを５枚必要な場合
12
+ // パターン①　12m巻でまかなうと、３ロール必要、8,000円ｘ3ロール=24,000円
13
+ // パターン②　30m巻でまかなうと、1ロール必要、19,000円x1ロール=19,000円
14
+ //
15
+ // この場合は、パターン②の30m巻を1ロール購入するのが正解です。
16
+ //
17
+ // 長さ5mを７枚必要な場合
18
+ // パターン①　12m巻のみでまかなうと、4ロール必要、8,000円x４ロール＝32,000円
19
+ // パターン②　30m巻のみでまかなうと、２ロール必要、19,000円x2ロール＝38,000円
20
+ // パターン③　30m巻と12m巻でまかなうと、30m巻1ロール、12m巻1ロール= 8,000円＋19,000円=27,000円
21
+ //
22
+ // この場合は、パターン③の30mと12mを組み合わせるパターンが最も安くなります。
23
+ //
24
+ // このような動的で最適なパターンの算出を行うために、どのような方法がありますでしょうか。
25
+ // どうかお知恵を貸してください。
26
+
27
+ public static void main(String[] args) {
28
+
29
+ // a=必要長さ (m)
30
+ // b=必要枚数 (枚)
31
+ // c=a*b=合計長さ (m)
32
+ // d=ロール (m)
33
+ // e=単価 (円)
34
+
35
+ //例題
36
+ //5x5
37
+ //5x7
38
+ //18x2
39
+
40
+ // 5m x 5枚必要
41
+ // 30m巻 x 1ロール = 19000円
42
+ // 最安値総計19000円
43
+
44
+ // 5m x 7枚必要
45
+ // 12m巻 x 4ロール = 32000円
46
+ // 最安値総計32000円
47
+
48
+ // 18m x 2枚必要
49
+ // 30m巻 x 2ロール = 38000円
50
+ // 最安値総計38000円
51
+
52
+ int a = 18;
53
+ int b = 2;
54
+ int c = a * b;
55
+
56
+ int[] d = { 12, 30 };
57
+ int[] e = { 8000, 19000 };
58
+
59
+ int[] ans = func(a, b, c, d, e);
60
+ int sum = 0;
61
+
62
+ System.out.println(a + "m x " + b + "枚必要");
63
+ for (int i = 0; i < ans.length; i++) {
64
+ if (ans[i] != 0) {
65
+ sum += ans[i] * e[i];
66
+ System.out.println(d[i] + "m巻 x " + ans[i] + "ロール = " + ans[i] * e[i] + "円");
67
+ }
68
+ }
69
+ System.out.println(" 最安値総計" + sum + "円");
70
+ }
71
+
72
+ static int[] func(int a, int b, int c, int[] d, int[] e) {
73
+
74
+ int n = d.length;
75
+ int[] result = new int[n];
76
+ int sum;
77
+ int x;
78
+ int[][] chk1 = new int[n][2];
79
+
80
+ //d0 //d1
81
+ //12 //30
82
+ //a5 b5
83
+ //c25
84
+
85
+ //d0 //d1
86
+ //12 //30
87
+ //a5 b7
88
+ //c35
89
+
90
+ //d0 //d1
91
+ //12 //30
92
+ //a18 b2
93
+ //c36
94
+
95
+ for (int i = 0; i < n; i++) {
96
+
97
+ if (d[i] < a) {
98
+ continue;
99
+ }
100
+
101
+ if (d[i] > c) {
102
+ chk1[i][0] = 1;
103
+ chk1[i][1] = e[i];
104
+ } else {
105
+ x = (int) Math.ceil(1.0 * b / (d[i] / a));
106
+ chk1[i][0] = x;
107
+ chk1[i][1] = e[i] * x;
108
+ }
109
+ }
110
+
111
+ int ans = 0;
112
+ for (int i = 0; i < n - 1; i++) {
113
+
114
+ if (chk1[i][1] == 0) {
115
+ ans = i + 1;
116
+ continue;
117
+ }
118
+
119
+ if (chk1[i][1] < chk1[i + 1][1]) {
120
+ ans = i;
121
+ } else {
122
+ ans = i + 1;
123
+ }
124
+ }
125
+
126
+ result[ans] = chk1[ans][0];
127
+ return result;
128
+ }
129
+ }
130
+ ```
131
+
132
+
133
+ ※以下初回分ですがコメント頂いているので残してます。
134
+ ---
135
+
1
136
  言語が何か分からないので自分の勉強のために例題としてjavaで実装してみました。
2
137
  if文とfor文くらいしか使ってないですが何かの参考になればと思います。
3
138
  5x5と5x7のケースしかテストしていません。

1

18x2に対応

2018/08/29 08:45

投稿

opyon
opyon

スコア1009

answer CHANGED
@@ -34,6 +34,7 @@
34
34
 
35
35
  ```java
36
36
 
37
+
37
38
  public class memo102 {
38
39
 
39
40
  // 長さ5mを５枚必要な場合
@@ -44,7 +45,7 @@
44
45
  //
45
46
  // 長さ5mを７枚必要な場合
46
47
  // パターン①　12m巻のみでまかなうと、4ロール必要、8,000円x４ロール＝32,000円
47
- // パターン②　30m巻のみでまかなうと、２ロール必要、22,000円x2ロール＝44,000円
48
+ // パターン②　30m巻のみでまかなうと、２ロール必要、22,000円x2ロール＝44,000円
48
49
  // パターン③　30m巻と12m巻でまかなうと、30m巻1ロール、12m巻1ロール= 8,000円＋22,000円=30,000円
49
50
  //
50
51
  // この場合は、パターン③の30mと12mを組み合わせるパターンが最も安くなります。
@@ -63,9 +64,10 @@
63
64
  //例題
64
65
  //5x5
65
66
  //5x7
67
+ //18x2
66
68
 
67
- int a = 5;
69
+ int a = 18;
68
- int b = 5;
70
+ int b = 2;
69
71
  int c = a * b;
70
72
 
71
73
  int[] d = { 12, 30, 60 };
@@ -88,6 +90,11 @@
88
90
  sum = 0;
89
91
  x = 0;
90
92
 
93
+ //追記
94
+ if(d[i]<a) {
95
+ continue;
96
+ }
97
+
91
98
  if (d[i] >= c) {
92
99
  x = (int) Math.ceil(c * 1.0 / d[i]);
93
100
  sum = x * e[i];
@@ -115,12 +122,24 @@
115
122
  continue;
116
123
  }
117
124
 
125
+ if(d[j]<a) {
126
+ continue;
127
+ }
128
+
129
+
118
130
  while (c > 0) {
119
131
  c = c - d[j];
120
132
  sum += e[j];
121
133
  tmp[j]++;
122
134
 
123
135
  if (c - d[j] < 0 && j != 0) {
136
+
137
+ //追記
138
+ if(d[j-1]<a) {
139
+ sum += e[j];
140
+ tmp[j]++;
141
+ }
142
+
124
143
  break;
125
144
  }
126
145
  }