[paiza]おやつは300円まで【殿堂入りキャンペーン】お菓子の詰め合わせ (paizaランク A 相当)

からあげクンもファミチキもおやつに入ります！

食べ盛りの頃はそう思ってた時期もありました（油しんどみ

面倒くさいので画面パタメータをListでもらった後のFunctionだけ

ちなみに引数のListを作ってる箇所はこっちの記事に書いてあるYO!!

schoolHiking.js

// [問題文（原文）]
// A 君は学校の遠足に持っていくお菓子を買わなければなりません。しかし、学校のルールにより、お菓子の総額は指定範囲内に収めなければなりません。
// そこで、指定金額ギリギリまで使って、なるべく色々な種類のお菓子を食べたいと思った A 君は買うお菓子を決めるために、学校のルールと自分の要望を踏まえて以下の基準を満たす買い方をすることにしました。
// 
// ・お菓子の総額を指定範囲内
// ・種類の数を最大にする
// ・同じお菓子は複数買わない
// ・お釣りを最小
// ・お釣りを最小にすることよりも種類の数を最大にすることを優先する
//
// お菓子の値段が書いてあるリストが与えられるので、A 君の代わりに、上記ルールを満たすお菓子の組み合わせを指定範囲内の最大の金額で買ったときのお釣りを求めてください。ただし、少なくとも一種類は指定範囲の値段で買えるものとします。
// 
// 入力例 1 の場合は、以下のように、指定範囲の金額で最大 2 個買えます。そして、そのうち最小になるお釣りの金額は 20 円になります。
function schoolHiking(lines) {
  // 入力は以下のフォーマットで与えられます。
  // 
  // N X
  // x_1
  // x_2
  // ...
  // x_N
  // 
  // 
  // ・ 1 行目にそれぞれ、選択できるお菓子の種類、指定制限金額を表す N, X が与えられます。
  // ・ 続く N 行のうちの i 行目 (1 ≦ i ≦ N) には、i 番目のお菓子の値段を表す整数が与えられます。
  // ・ 入力は合計で N + 1 行となり、入力値最終行の末尾に改行が １ つ入ります。
  const [cnt, max] = lines[0].split(' ').map(Number);
  const prices = lines.slice(1).map(Number);

  // dp[i][j] は j 円を使って i 種類のお菓子を選んだときの最大使用金額
  let dp = Array.from({ length: cnt + 1 }, () => Array(max + 1).fill(-1));
  dp[0][0] = 0;

  // 金額が小さい順に並び替える
  prices.sort((a, b) => a - b);

  // dpの生成
  for (let price of prices) {
    for (let i = cnt; i > 0; i--) {
      for (let j = max; j >= price; j--) {
        if (dp[i - 1][j - price] !== -1) {
          dp[i][j] = Math.max(dp[i][j], dp[i - 1][j - price] + price);
        }
      }
    }
  }

  // 最大購入数と最大購入費
  let maxCount = 0,  maxAmount = 0;
  for (let i = 0; i <= cnt; i++) {
    for (let j = 0; j <= max; j++) {
      if (dp[i][j] !== -1) {
        // 購入数を優先する
        if (i > maxCount || (i === maxCount && dp[i][j] > maxAmount)) {
          maxCount = i;
          maxAmount = dp[i][j];
        }
      }
    }
  }

  console.log(max - maxAmount);
}

module.exports = {
  schoolHiking
};

動的計画法（ナップサック問題）

指定された条件に基づいてお菓子の組み合わせを決定し、最大の種類数と指定範囲内の合計金額を満たすようにしなくてはならないので、とりあえず総組み合わせから1個・2個・3個買った時におイクラ万円かかるのかを割り出して、
その中から最大数と最大使用金額を求めるような組み合わせを探すような作りにしてます。

逆順（i--とかj--）ループしてるのは、

• 同一金額のお菓子が複数回登場しても、各ステップで独立した状態更新が保証するため
• 既に更新された状態が次の更新に影響を与えないため
  この方法により、同じお菓子を複数回使用することを防ぎ、動的計画法の正確な結果を得ることができるんだって。

調べながら作ったので、動的計画法ってな～に？って感じでしたが、
なんとか動くものが作れたからよし！

ちなみに

最後の結果を以下のように変えて、ちゃんと最大数で割り出してるか検証してみた
console.log(max - maxAmount, maxCount, maxAmount);

テストケース1(同一お釣り合計が280になるパターンが2つ有るケース)

5 300
150
120
130
75
55
20 3 280

ちゃんと150 + 75 + 55の3つを購入してるという動きになったのでよし！

テストケース2(最大お釣りは少ないけど、購入数が勝ってるケース)

5 300
150
120
130
70
55
25 3 275

最大お釣りは150 + 130の2つ購入の20だけど、
ちゃんと150 + 70 + 55の3つを購入してるという動きになったのでよし！