金庫盗難（DP，Knapsack）

質問する

東京はアルゴリズムを使ってtarget金額を盗むことができる数を計算します.
たとえば、$50を盗むときに$10、$20、および$50がある場合は、以下の4つの方法で$50を盗むことができます.

ドル50

を1枚盗む
2枚

ドル20、1枚10

を盗む
1枚

$20、3枚盗んで$10

ドル10 5枚

盗みたいtargetの金額と金庫の中のお金のタイプを入力し、東京に戻ってtargetの数を盗むことができます.

入力

パラメータ1:target

番号タイプの100000以下の自然数

パラメータ2:type

番号タイプ要素の100以下の自然数の配列

しゅつりょく

番号タイプを返さなければなりません.

ジョージは、ターゲットを盗むことができる数を数字で返します.

注意事項

すべての通貨が無限であると仮定します.

I/O例

マイコード

ダイナミックプランニング(Dynamic Programing,DP)を利用する.与えられた問題をそれぞれの場合の数字に分割することができ、次の場合の数字を求めるために用いることができるので、繰返し演算を最小化することができる.
目標金額は50で、お金の種類は[10,20,50]なので、例を挙げます.
もしあなたが3種類のお金を持っていて、3種類のお金で目標の金額を盗むことができたら、数量を手に入れなければなりません.
つまり10元のとき20元のとき10元+20元のとき...など、動的プランニング法を使用して状況の数を小さい数に分割し、最終的に状況の数をすべて統合する根拠を作成しました.
0元10元20元30元40元50元10元50元
表の横線は、0元からターゲット金額までのすべての盗難可能な金額です.
切符の縦は与えられたお金の種類(10元、20元、50元)です.
まず、目標金額の50元だけ10元を盗む場合を考えてみます.
0元10元20元30元40元50元10元120元150元1
与えられたお金で0元を盗むと、全然盗まないことがあるので、1です.
10元盗めば、数は10元、50元の1を盗む.(10元1個、10元5個)
0元10元20元30元40元50元10元111120元150元1
20元で目標金額を盗む場合、目標金額が20元の場合、40元の場合.
0元10元20元30元40元50元10元1111120元10101050元1
しかし、10元と20元で目標金額を盗む場合は違います.
目標金額が30元の場合(10元+20元)、50元の場合(10元1個+20元2個、10元3個+20元1個).また、40元(2個10元+20元1個)の場合も可能です.
10元と20元の場合、数量は以下の通りです.
0元10元20元30元40元50元10元11111120元1123350元1
50元も同じで、以下の通りです.
50元
0元10元20元30元40元50元10元11111120元1123350元1000001
10元と50元です.
0元10元20元30元40元50元10元11111120元1123350元11112
10元20元50元盗む
0元10元20元30元40元50元10元11111120元1123350元11234
つまり、10元、20元、50元で50元盗める場合の数は4つです.
規則性のセットがあります.기존 경우의 수에 현재 돈의 종류를 뺀 경우의 수를 더하는 것です.
何も盗まない限り、

50元盗んだ場合は[0,0,0,0,1]です

10元と50元を盗んだ場合、10元と50元のうち後ろのお金の種類(50元)を抜いた場合、つまり10元を盗んだ場合、[1,1,1,1,1]

この2つのケースを加えると、[1,1,1,1,2]が発生します.

10元、20元、50元を盗む場合も同様で、50元を盗む場合は[0,0,0,0,1]と

10元、20元盗むと[1,2,2,3,3]が加算されます.

コードは次のとおりです.

結果

ソースコード

function moneyHeist(target, type) {
  // 목표 금액 + 1을 길이로 새로운 배열을 만듭니다.
  // 경우의 수를 저장하기 위해 최초로 0을 할당합니다.
  // 배열의 인덱스는 목표 금액이 됩니다.
  // 목표 금액이 0인 경우는 아무것도 훔치지 않는 경우가 있으므로
  // 0번째 인덱스 값을 1로 할당합니다.
  let dp = new Array(target + 1).fill(0);
  dp[0] = 1;
  for (let i = 0; i < type.length; i++) {
    // 돈의 종류로 들어온 배열을 반복 순회합니다.
    // 만약 10원으로 10원을 만드는 경우는 오직 1개이므로
    // 그 값을 인덱스로 가지는 dp 배열에 1을 증가시킵니다.
    dp[type[i]] += 1;
    for (let j = type[i] + 1; j <= target; j++) {
      // 10원과 20원으로 20원을 만드는 경우는
      // 20원만으로 20원을 만드는 경우에
      // 10원만으로 20원을 만드는 경우를 더해야합니다.
      dp[j] += dp[j - type[i]];
    }
  }
  return dp[target];
}