そのデッキは本当に最強なのか？

ソーシャルゲームに携わって結構な月日が流れましたが
その大半が俗にいうところの『カードゲーム』でした。

で、カードゲームとなると気になるのが
『ぼくのかんがえたさいきょうのデッキ』なわけです。

『おすすめ編成』みたいな機能は割とよく見かけるので、
サーバサイドで何かしらロジックは組まれていると思うんですが、
よくよく思い返してみると、コードそのものを見たことないなーと気づきました。
(ソーシャルではフロント担当ばっかりなので)

果たしてどんな感じなんだろう？　と気になってしまったので・・・
**デッキ内のカードの攻撃力が最大となるような組み合わせ**を求めるコードを
ソーシャルで(少なくとも自分が関わった中では)よく使われるPHPで考えてみました。

# アルゴリズムを考える
まずはいろいろと考えてみたんですが
総当たりにならないパターンでは

- 攻撃力順に並べて上から入れ、余ったコストに入るカードを入れる
- 単位コストあたりの攻撃力の高い順から埋める

などがありそうですが、どちらも余剰コストの埋め方・本当にそのカードが入っていていいのかetc...
といった問題が出てきそうなので、基本は総当たりになりそうなんですよね・・・


## 『ナップサック問題』がいい感じ
で、調べたらすぐに出てきてしまったんですが、
[ナップサック問題](https://ja.wikipedia.org/wiki/%E3%83%8A%E3%83%83%E3%83%97%E3%82%B5%E3%83%83%E3%82%AF%E5%95%8F%E9%A1%8C)というのがかなりいい感じです！

このアルゴリズムを一言で言うと

1. 各アイテムを『入れた場合』と『入れない場合』のパターンを再帰的に調べる
2. 1の結果のうち、結果が理想に近いほうを採用する
2. メモを使って、過去に試した組み合わせは処理を短縮

といった感じでしょうか？


ただ、wikiの例示をそのままだと

- 最大の容量合計を算出しているので、**容量＝価値の時しか使えない**
- 求めるものが『入れるアイテムの容量合計の最大値』なので、**どのアイテムを使ったが分からない**

といった事になってしまうので、手を加える必要がありますね。

## どこに手を加えるか
カードゲームのデッキにある要素と比較すると

| カードゲーム       |ナップサック問題|
|:-----------------|------------------:|
| デッキの最大コスト|ナップサック容量|
| デッキの最大枚数|？？？| |
| カードのコスト|アイテムの容量|
| カードの強さ| ？？？|

みたいな対応になりそうなので、
？？？に該当する個所をアルゴリズムに加えてあげればよさそうです。

# というわけで

できあがったものが[こちら](https://github.com/tawaship/etc/blob/master/Knapsack.php)です！
(キュー〇ー3分クッキングのテーマに乗せて)

## 使い方

```PHP
$knapsack = new Knapsack([デッキ最大コスト], [カードのコスト配列], [カードの攻撃力配列], [デッキに入れられる最大枚数]);
$res = $knapsack->getMaxCombination();
```
で、$resに最高の組み合わせが格納されます。

試しに以下。

```PHP
$cardList  = array(
	array('cost' => 50,  'attack' => 1564),
	array('cost' => 20,  'attack' => 333),
	array('cost' => 6,   'attack' => 1923),
	array('cost' => 9,   'attack' => 8913),
	array('cost' => 3,   'attack' => 892),
	array('cost' => 12,  'attack' => 320),
	array('cost' => 88,  'attack' => 38117),
	array('cost' => 65,  'attack' => 23444),
	array('cost' => 15,  'attack' => 1564),
	array('cost' => 487, 'attack' => 15239),
	array('cost' => 43,  'attack' => 8523),
	array('cost' => 6,   'attack' => 5006),
);

$capacities  = array();
$values      = array();
foreach ($cardList as $value) {
	$capacities[] = $value['cost'];
	$values[]     = $value['attack'];
}
	
$maxCost  = 110; // デッキの最大コスト
$maxCount = 6;   // デッキに入れられる最大枚数
$knapsack = new Knapsack($maxCost, $capacities, $values, $maxCount);
$res = $knapsack->getMaxCombination();

echo implode(",",$res->keys); // 11,6,3,2
echo $res->sum;               // 53959
```

検算がどうしたものか、というところなのですが


```PHP
$max = 0;          // メモの中の攻撃力合計の最大値
$f = array();      // $maxに対応するcardListのindex組み合わせ
$c = 0;            // $maxの時の合計コスト

foreach ($knapsack->_memory as $value) {
	foreach ($value as $key2 => $value2) {
		if ($max < $value2->sum) {
			$max = $value2->sum;
			$c = $key2;
			$f= $value2->keys;
		}
	}
}

echo $max;              // 53959
echo implode(",", $f);  // 11,6,3,2
echo $c;                // 110
```

となりましたので、上手くいっている・・・？　と思います！
※チェック用に $knapsack->_memory を publicに変えてます


## 注意点

1. **[カードのコスト配列] と [カードの攻撃力配列] は0から始まる添え字配列にする**
2. **あるカードのコスト・攻撃力は　[カードのコスト配列] と [カードの攻撃力配列] の同じindexに入れる**

どちらもアルゴリズム側の都合になるんですが、
処理中の配列index参照を、0からのインクリメントで行っている、というのと
コストと攻撃力のindexが一致していないと、対応するデータの参照ができないから、です。

引数をコストと攻撃で別配列に分けず、$cardListをそのまま引数に受けることも考えましたが、
コストや攻撃力に対応する配列キー名が外部データ依存(大体DBのカラム名？)なので
この形に落ち着きました。


# まとめ
実際のゲームで考えると、
スキル効果があったり、属性での有利不利があったり、
そもそも攻撃力だけで考えていいのかーみたいな問題が山積みなのですが
今回のを基本に据えれば、割といろいろできそうですね～。

みんなもカードゲーム遊んでね！