動的プログラミングを用いた詳細解析と可視化
3種類のりんごセット（x個/a円、y個/b円、z個/c円）を使って、n個以上のりんごを最小コストで購入する
/**
* n個以上のりんごを最小コストで購入するための金額を計算する
* 動的プログラミングを使用して効率的に解を求める
*/
function minCostForApples(n, x, a, y, b, z, c) {
// 効率的な上限を設定（計算量とメモリ使用量を最適化）
const maxApples = n + Math.max(x, y, z) - 1;
// DPテーブルを初期化（Int32Arrayの範囲内でINFを設定）
const INF = 2147483647; // Int32Arrayの最大値
const dp = new Int32Array(maxApples + 1);
dp.fill(INF);
dp[0] = 0; // 0個の場合はコスト0
// 動的プログラミングで最小コストを計算
for (let i = 0; i <= maxApples; i++) {
if (dp[i] === INF) continue;
const currentCost = dp[i];
// セット1（x個でa円）を使う場合
if (i + x <= maxApples) {
dp[i + x] = Math.min(dp[i + x], currentCost + a);
}
// セット2（y個でb円）を使う場合
if (i + y <= maxApples) {
dp[i + y] = Math.min(dp[i + y], currentCost + b);
}
// セット3（z個でc円）を使う場合
if (i + z <= maxApples) {
dp[i + z] = Math.min(dp[i + z], currentCost + c);
}
}
// n個以上のりんごを手に入れる最小コストを求める
let minCost = INF;
for (let i = n; i <= maxApples; i++) {
if (dp[i] < minCost) {
minCost = dp[i];
}
}
return minCost;
}dp[0] = 0（0個のりんごを手に入れるコストは0円）
他の全ての要素はINFで初期化
各状態 i から3つのセット購入を試行:
dp[i+x] = min(dp[i+x], dp[i] + a)dp[i+y] = min(dp[i+y], dp[i] + b)dp[i+z] = min(dp[i+z], dp[i] + c)dp[n]からdp[maxApples]までの最小値を求める
| 個数 | 0 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 |
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| 初期 | 0 | ∞ | ∞ | ∞ | ∞ | ∞ | ∞ | ∞ | ∞ | ∞ | ∞ | ∞ | ∞ |
| i=0後 | 0 | 100 | 125 | ∞ | 200 | ∞ | ∞ | ∞ | ∞ | ∞ | ∞ | ∞ | ∞ |
| i=2後 | 0 | 100 | 125 | 200 | 200 | 225 | ∞ | 300 | ∞ | ∞ | ∞ | ∞ | ∞ |
| i=3後 | 0 | 100 | 125 | 200 | 200 | 225 | 250 | 300 | 325 | 250 | ∞ | ∞ | ∞ |
| 最終 | 0 | 100 | 125 | 200 | 200 | 225 | 250 | 300 | 325 | 250 | 350 | 350 | 375 |
最小コスト: 375円 (セット2を3回購入)
INF値は2147483647（2³¹-1）に設定してオーバーフローを防止
外側ループ: O(n + max(x,y,z)) ≈ O(n)
内側処理: O(1) × 3回の遷移チェック
総計算量: O(n × max(x,y,z))
DPテーブル: O(n + max(x,y,z))のInt32Array
補助変数: O(1)
総メモリ使用量: O(n + max(x,y,z))
| n | 結果 | 時間(ms) | メモリ(KB) |
|---|---|---|---|
| テストを実行してください | |||