概要
アルゴリズムを学習をした際の記録を投稿します。
今回は蟻本p67動的計画法の重複組合せについてです。
問題
n種類の品物があり、i番目の品物はai個あります。異なる種類の品物同士は区別できますが、同じ種類の品
物同士は区別できません。これらの品物の中からm個選ぶ組み合わせの総数を求め、Mで割った余りを答えなさい。
入力
n = 3
m = 3
a = [1,2,3]
M = 10000
出力
6
コード部分
//
/**
* pp67 重複組み合わせ
* @param n {Number} 品物の種類
* @param m {Number} 選ぶ個数
* @param a{Array} i番目の個数
* @return {Number} 組み合わせの総数
*/
const cal = (n,m,a) =>{
let dp = new Array(n + 1).fill(null).map(() => new Array(m + 1).fill(0));
for(let i=0;i <= n; i++){
dp[i][0] = 1;
}
let loopCount = 0;
console.log(`ループ数|i|j|条件|dp[i+1][j]の計算式|dp[i+1][j]の値`);
console.log(`--|--|-----|----|-----|---`);
for(let i=0; i < n; i++){
for(let j=1; j<=m; j++){
loopCount++;
if(j - 1 - a[i] >= 0){
dp[i+1][j] = dp[i+1][j-1] +dp[i][j]-dp[i][j-1-a[i]]
console.log(`${loopCount}|${i} | ${j} | j - 1 - a[i] >= 0 </br> ${j} - ${1} - a[${i}] ( =${a[i]}) >= 0 | dp[i+1][j-1] +dp[i][j]-dp[i][j-1-a[i]]</br>dp[${i}+1][${j}-1]( = ${dp[i+1][j-1]}) + dp[${i}][${j}]( = ${dp[i][j]}) - dp[${i}][${j}-1-a[${i}]]( = ${dp[i][j-1-a[i]]}) | dp[${i+1}][${j}] = ${dp[i+1][j]}`)
}else{
dp[i+1][j] = dp[i+1][j-1] +dp[i][j];
console.log(`${loopCount}|${i} | ${j} | j - 1 - a[i] < 0 </br> ${j} - ${1} - a[${i}] ( =${a[i]}) < 0 | dp[i+1][j-1] +dp[i][j]</br>dp[${i}+1][${j}-1]( = ${dp[i+1][j-1]}) + dp[${i}][${j}]( = ${dp[i][j]}) | dp[${i+1}][${j}] = ${dp[i+1][j]}`)
}
}
}
console.log(dp);
return dp[n][m];
}
// 結果値は結果値は6
console.log(cal(3,3,[1,2,3]));
python tutor
コードを実際に動かせるwebサイト
ステップ実行かつステップ事の変数を確認できる特徴があります。
その他情報
感想
動的計画法に関しては漸化式を決めるのが難しいですね。
実装の方法については見慣れましたね。
依存関係グラフ
依存関係グラフは変数の結びつきを一目でわかりやすくするための図です。
変数の流れを確認しやすくすることでワーキングメモリの負担を減らすことができます。
作成方法はコード上の変数に丸付けて線を繋げています。
状態遷移図
計算内容を明示する表。
ステップごとの変数の値を各列に表示します。
複雑な計算を行うコードを理解するのに役立つ表です。
| ループ数 | i | j | 条件 | dp[i+1][j]の計算式 | dp[i+1][j]の値 |
|---|---|---|---|---|---|
| 1 | 0 | 1 | j - 1 - a[i] < 0 1 - 1 - a[0] ( =1) < 0 | dp[i+1][j-1] +dp[i][j]dp[0+1][1-1]( = 1) + dp[0][1]( = 0) | dp[1][1] = 1 |
| 2 | 0 | 2 | j - 1 - a[i] >= 0 2 - 1 - a[0] ( =1) >= 0 | dp[i+1][j-1] +dp[i][j]-dp[i][j-1-a[i]]dp[0+1][2-1]( = 1) + dp[0][2]( = 0) - dp[0][2-1-a[0]]( = 1) | dp[1][2] = 0 |
| 3 | 0 | 3 | j - 1 - a[i] >= 0 3 - 1 - a[0] ( =1) >= 0 | dp[i+1][j-1] +dp[i][j]-dp[i][j-1-a[i]]dp[0+1][3-1]( = 0) + dp[0][3]( = 0) - dp[0][3-1-a[0]]( = 0) | dp[1][3] = 0 |
| 4 | 1 | 1 | j - 1 - a[i] < 0 1 - 1 - a[1] ( =2) < 0 | dp[i+1][j-1] +dp[i][j]dp[1+1][1-1]( = 1) + dp[1][1]( = 1) | dp[2][1] = 2 |
| 5 | 1 | 2 | j - 1 - a[i] < 0 2 - 1 - a[1] ( =2) < 0 | dp[i+1][j-1] +dp[i][j]dp[1+1][2-1]( = 2) + dp[1][2]( = 0) | dp[2][2] = 2 |
| 6 | 1 | 3 | j - 1 - a[i] >= 0 3 - 1 - a[1] ( =2) >= 0 | dp[i+1][j-1] +dp[i][j]-dp[i][j-1-a[i]]dp[1+1][3-1]( = 2) + dp[1][3]( = 0) - dp[1][3-1-a[1]]( = 1) | dp[2][3] = 1 |
| 7 | 2 | 1 | j - 1 - a[i] < 0 1 - 1 - a[2] ( =3) < 0 | dp[i+1][j-1] +dp[i][j]dp[2+1][1-1]( = 1) + dp[2][1]( = 2) | dp[3][1] = 3 |
| 8 | 2 | 2 | j - 1 - a[i] < 0 2 - 1 - a[2] ( =3) < 0 | dp[i+1][j-1] +dp[i][j]dp[2+1][2-1]( = 3) + dp[2][2]( = 2) | dp[3][2] = 5 |
| 9 | 2 | 3 | j - 1 - a[i] < 0 3 - 1 - a[2] ( =3) < 0 | dp[i+1][j-1] +dp[i][j]dp[2+1][3-1]( = 5) + dp[2][3]( = 1) | dp[3][3] = 6 |
[ [ 1, 0, 0, 0 ],
[ 1, 1, 0, 0 ],
[ 1, 2, 2, 1 ],
[ 1, 3, 5, 6 ] ]
dpテーブルの図
手書き数字はループ数
参考資料
プログラミングコンテストチャレンジブック [第2版] マイナビ p67
プログラマー脳 秀和システム
p73 python tutor
p71 状態遷移表
p69 依存関係グラフ
githubコミット部分