私自身が表題の問題を解いた時のプログラムについて解説します。
問題の詳細は「最強のデッキを構築しよう！」（CodeIQ）を参照してください。
あなたはとあるゲームの開発者で、あるカードゲームのアルゴリズムを任されました。
その内容は、「デッキ」と呼ばれるカードの組み合わせを自動的に構築するというもの。
といっても、カードは適当に選んで良いわけではなく、なるべくデッキが強くなるような組み合わせを求める必要があります。
前提となる条件は以下の通りとなります。
それでは、入力と出力例を示しましょう。
- コストとスコアがそれぞれci, si となるようなN枚のカードがある。iはカード番号を差し、i=1,2...Nとする
- デッキは、1枚以上M枚以下のiが異なるカードで構築するものとする。上限枚数(M)を超えてはならない
- デッキ内のカードは、その合計コストが最大コスト(C)を超えてはならない
- デッキの上限カード枚数(M)は、2以上5以下とする
- デッキの最大コスト(C)は1以上500以下の整数とする
- カードの枚数(N)は5以上、1000以下とする
- 各カードのコスト(ci)は、1以上50以下の整数であり、最大で7種類とする
- 各カードのスコア(si)は、1以上1000以下の整数とする
- 上記制約のもとに、合計スコアが最大となるデッキを求めること
以下、カードのコストとスコアをテーブルで示したものです。
コスト スコア カード1 25 30 カード2 15 15 カード3 10 20 カード4 5 1
この例では、N=4, M=2, C=30, c={25, 15, 10, 5}, s={30, 15, 20, 1} となり、カード2, 3を選択すると、合計コスト30以下で合計スコアを15+20=35と最大化できる、というわけですね。
次にプログラムの仕様ですが、標準入力からデッキのカード上限枚数（1行目）と、デッキの最大コスト（２行目）、そしてN枚のカードのステータス（コスト、スコアの順にスペース区切り、3行目以降）が与えられます。
標準出力に、求めたデッキのスコア合計値と改行を返してください。いずれの値も整数となります。
上記の例においては、以下のように35と返すのが正しい結果となります。
Rubyで解答しています。
#!/usr/bin/ruby
$DECK = 0 # 最大枚数
$COST = 0 # 最大コスト
$CARDS = Hash.new([].freeze) # カードのリスト。キーはコスト。値はスコアの配列
$Pattern = [] # 指定された枚数でのカードの組み合わせパターン
# カードをコストごとに降順にソートする
def sortCards()
$CARDS.each{|c, ss|
$CARDS[c] = ss.sort{|a,b| b <=> a }
}
end
# 指定された枚数以下でコストによる可能な組み合わせリストを生成する
# 組み合わせのコスト合計が指定を超えるものは使用しない
def makePattern()
for i in 1..$DECK
$CARDS.keys.repeated_combination(i){|arr|
if arr.reduce(:+) <= $COST then $Pattern << arr end
}
end
end
# コストの組み合わせに従ってスコアを計算する
# カードリストはコストごとにスコアで降順に並んでいるので先頭から順に使用すれば、その組み合わせで最大のスコアに成る
def totalScore(pattern)
used = {} # 使用したカード番号を記録する
for k in $CARDS.keys
used[k] = 0
end
ret = 0
for c in pattern
n = used[c] # 使用可能な最も先頭のカード
# そのコストのカードがなくなっている場合は0を加える
ret += ($CARDS[c][n] == nil ? 0 : $CARDS[c][n])
# カードを使用済みにする
used[c] += 1
end
# puts pattern.to_s + " = " + ret.to_s
return ret
end
# 問題を解く
def solve()
results = []
for pt in $Pattern
results << totalScore(pt)
end
return results.max
end
# main
lc = 0
while line = gets
line.strip!
if line.empty? then next end
if lc == 0 then
$DECK = line.to_i
elsif lc == 1 then
$COST = line.to_i
else
cs = line.split(" ").map{|c| c.to_i}
$CARDS[cs[0]] += [cs[1]]
end
lc += 1
end
sortCards()
makePattern()
p solve()
この問題は一見ナップザック問題の変形に見えますが違います。
この問題のコストを重さ、スコアを価値に変えるといかにもナップザック問題に見えます。私も問題を読んだ瞬間「ナップザック問題の変形」だな、と思いました。しかし、この問題には制約条件としてデッキの枚数があります。
これが曲者でナップザック問題の手法では解けません。できるかもしれませんが私の能力ではうまいアルゴリズムを思いつきません。ちょっと具体例を示しましょう。
例のパラメータを少しいじります。
| コスト | スコア | |
|---|---|---|
| カード1 | 25 | 30 |
| カード2 | 15 | 14 |
| カード3 | 10 | 20 |
| カード4 | 5 | 5 |
この問題の条件で気になるのが「各カードのコスト(ci)は、1以上50以下の整数であり、最大で7種類とする」の下線部分です。
コストが最大7パターンしかなく、デッキの最大枚数が5枚なのでカードが十分な枚数あるとした場合、コストのみに注目すると最大で75の組み合わせしかありません。これは総当たり可能な数です。
そして、同じコストのカードならスコアの高いものから優先的に使えばスコアを最大化できます。
つまり、次の手順で答えを求めることができます。
入力値をパースして値を大域変数に取ります。
$DECKはカードの最大枚数、$COSTは最大コストです。
カードは$CARDSに保持しますが、これはキーをカードのコスト、値をカードのスコアの配列として保持します。
そしてsortCards()で同じコストのカードを降順にソートし、先頭からスコアの高い順に取得できるようにします。（ソートするだけなので説明は省略します）
次にmakePattern()で候補となるカードの組み合わせをコストに基づいて作成します。
あとはsolve()で各組み合わせのスコア合計を計算し、結果を出力します。
「基本的な考え方」に書いた通り、コストに基づいてカードの組み合わせを作ります。同じコストのカードが複数あるので重複組み合わせを求めます。注意すべき点はカードの最大枚数は制限されていますが、その枚数以下であれば良いので組み合わせの数は1〜最大枚数（2〜最大枚数で問題ない気もします）で作る必要があるということです。
Rubyには重複組み合わせを列挙するrepeated_combination()があるので簡単に列挙できます。
実際に入力されるカードの枚数には上限があり、実際には構築できない組み合わせもできてしまいますがここでは無視します。
コストの合計が制限を超えるものは省いてしまいます。
解を求める関数です。
カードの組み合わせ候補のスコアの合計はtotalScore()で計算します。
その結果の中で最大のものを返します。
引数patternに渡されたカードの組み合わせのスコアの合計を計算します。
30〜32行目で作っているのは使用したカードの枚数を記録するための連想配列でキーはカードのコスト、値は使用済みのカードの枚数です。
35〜43行目でカードの組み合わせに従ってコストを合計します。$CARDSはキーをカードのコスト、値は降順にソートされたスコアの配列なのでpatternの各コストの配列を取得し、usedの値でアクセスすればスコアの高い順にカードを選ぶことができます。この時、要素がなければ（つまりそのコストのカードを使い切っていたら）0を加算します。makePattern()でカード枚数をチェックするよりもこちらの方が処理が単純になります。
合計を計算したら使用済みのカードを1増やします。
最終的に合計値を返します。
本文にも書いた通り、当初は複数の制限事項があるナップザック問題として解き、計算を効率化するためにコストが7通りしかないという仕様を使おうと思っていました。
最初から「コストが最大7パターン」という妙な条件は気になっていたのですが、問題があまりにもナップザック問題風だったため、なかなかその方向から頭を切り替えることができず結構時間がかかりました。