# 問題解決力を鍛える！アルゴリズムとデータ構造

## 第5章

- 5.3と5.4を読む
- 任意参加
- ファシリテーター: tsujita

### 話す・書く順番決めルーレット

in Ruby

['hsu', 'chen', 'teruya', 'kanazawa', 'okura', 'tsujita'].shuffle.each { |v| puts ">[name=#{v}]\n\n" }

in JavaScript

const l = ['hsu', 'chen', 'teruya', 'kanazawa', 'okura', 'tsujita']
l[Math.floor(Math.random()*l.length)]

### ファシリテーター決め方

- `%w(hsu chen teruya kanazawa okura kanno)`の順番でやっていく

### 参加者がやること
- 事前に決められた章を読む
- 学んだことやわからなかったことを書き込む（任意）

当日
- 最初に感想や質問を書く時間を設ける(10分)
- 時間枠 60分
- 延長枠 30分

### 勉強会時にやること

各自学びや気付き、疑問を発表していく
ファシリテーターがよしなに議論を進める
終了前に勉強会を振り返る？（KPTなどで）← 60分のときに仮締め

## 各自が書き込む場所
>[name=tsujita]

> code 5.3 Frog問題を「緩和」を意識した動的計画法で解く

- 5.7の図をコードにしている
- 28行めでINFと1つ前から来た場合を比較
- 30行めで28行目の勝者と2つ前からきた場合を比較

> code 5.4 Frog問題を「配る遷移形式」で解く

- 配る→先を埋めていく
- 29行め i の一つ先を埋める
- 32行め i の二つ先を埋める

ループの中のそれぞれ隣り合う別のターンで2個前から来た時と1個前から来たときの比較が行われていく

> ナップサック問題に対する動的計画法

添字の概念がよくわからなかったです・・
二重配列の要素取得に見えてしまう

things = [[2,3], [1,2], [3,6], [2,1], [1,3], [5,85]]
N = things.size
C = 15

pp dp = Array.new(N + 1){Array.new(C + 1, 0)}

(0...N).each do |n|
  cost, value = things[n]
  (0..C).each do |c|
    dp[n+1][c] = [dp[n+1][c], dp[n][c]].max
    if (c+cost) <= C
      dp[n+1][c+cost] = [dp[n+1][c+cost], dp[n][c]+value].max
    end
  end
end

>[name=chen]

5.4 動的計画法の例(1)：ナップサック問題

図 5.10 の問題をjavascriptで解きたいんですが、うまくできないのかな :thinking_face:

const input = [
	{weight: 2, value:3},
	{weight: 1, value:2},
	{weight: 3, value:6},
	{weight: 2, value:1},
	{weight: 1, value:3},
	{weight: 5, value:85},
]
const arrW = input.map(item => item.weight)
const arrV = input.map(item => item.value)

console.log(arrW)
console.log(arrV)
// arrW: [2, 1, 3, 2, 1, 5]
// arrV: [3, 2, 6, 1, 3, 85]

// Uncaught TypeError: Cannot read properties of undefined (reading '0')
// ここで壁にぶつかる...dpをどうやって定義したほうが正しい？
const dp = []

for(var i = 0; i < input.length; ++i){
  for(var w = 0; w <= 15; ++w){
    if(w - arrW[i] >= 0){
      dp.push(Math.max(dp[i+1][w], dp[i][w - arrW[i]] + arrV[i]))
    } 
    dp.push(Math.max(dp[i+1][w], dp[i][w]))
  }
}

console.log(dp)

>[name=teruya]

図　5.10

## 振り返り
>[name=tsujita]

めちゃくちゃ難しかったですが楽しかったです🙋🏻‍♀️！！！

>[name=chen]

買い物の方法で説明するのが楽して面白かった！www
よく理解できました！

>[name=teruya]

今回みたいな二次元DPが書けたらもう最強です…

## 終了後ファシリテーターがやること
- 次回のファシリテーターを決める
- hsuさん(?)
- 読む範囲を決める
- 5,5と　５、６