ここ最近、Knapsack Problemが流行っている感じがしています。

応用情報技術者過去問題 平成29年春期 午後問3では基本「全探索」、改善提案が「枝刈り」でしたが、それでは全然不十分です。この問題は要するにKnapsack Problemのちょっとした変形で、code量もさしたることなく書けますし、折角FEではなくAPなのだし、日本の若者のためにも、Knapsackで書くよう誘導すべきだったのでは、と「禿げしく」思ったものでした。

すると、今度は応用情報技術者過去問題 平成29年秋期 午後問3でKnapsack Problemを正面から出してきましたね。0-1ではなく普通の。ぼくは前回のrevengeではないかと思ってみています。 問題自体は、あまりにも普通のKnapsack Problemなので、ツッコミようがなくてつまんなかったデス。

この他にアジアでも。そっちは0-1でした。

References

• WikipediaEn, Ja
• Aizu Online Judge
• 「最強最速アルゴリズマー養成講座」最新記事一覧, 病みつきになる「動的計画法」、その深淵に迫る, アルゴリズマーの登竜門、「動的計画法・メモ化再帰」はこんなに簡単だった
• 片鱗懐古のブログ 01ナップサック問題を動的計画法で解く場合の考え方
• 【Java】ナップサック問題(knapsack)[動的計画法]

ちなみに日本語では「ナップザック」、登山用語はドイツから入ってきたから、です。