動的計画法の基礎：バックパック問題の完全解説
バックパック問題は動的計画法（DP）の最も古典的で基礎的な問題の一つです。多くのアルゴリズム学習者の「必修科目」とも言えるこの問題は、見た目は単純（バックパックに荷物を詰めて価値を最大化する）ですが、01バックパック、完全バックパック、多重バックパックなど多くのバリエーションに派生し、DPの核心思想が体系全体に貫かれています。本記事では、01バックパックから始め、各種バックパック問題の原理、状態遷移、コード実装を段階的に解説し、バックパックDPを完全に理解してもらうことを目指します。
1. バックパックDPの核心思想
バックパックDPの核心は、容量制限内で物品を選択し、総価値を最大化することです。具体的には、容量 maxCapacity のバックパックと numItems 個の物品があり、各物品には重量 weights[i] と価値 values[i] が設定されています。目標は、総重量が maxCapacity を超えないように物品を選択し、総価値を最大にすることです。
DPの解決策は「部分問題の分割 + 状態の記録 + 状態遷移」であり、バックパックDPも例外ではありません。
- 状態定義：
dpTable[i][j]を「最初のi個の物品を、容量jのバックパックに詰めた場合の最大価値」と定義します。 - 状態遷移：
i番目の物品に対して、「選ぶ」か「選ばない」かの2つの選択肢があり、その最大値を取ります。 - 初期状態：物品が0個の場合、またはバックパックの容量が0の場合、価値は0です。
2. 基礎：01バックパック（各物品は1回のみ選択可能）
01バックパックは最も基本的な形式です。「01」は「選択（1）」か「非選択（0）」の2つの状態を意味します。
2.1. 二次元配列による01バックパックの実装
まず、二次元配列を使用した実装を理解しましょう。これは概念を把握するのに役立ちます。
状態定義
dpTable[i][j]：最初の i 個の物品を、容量 j のバックパックに詰めた場合の最大価値。
状態遷移
i 番目の物品について考えると、2つの選択肢があります。
- 選ばない：
dpTable[i][j] = dpTable[i-1][j]（価値はi-1個の物品の時と同じ）。 - 選ぶ：
j >= weights[i]であることが前提で、dpTable[i][j] = dpTable[i-1][j - weights[i]] + values[i]（容量から現在の物品の重量を引いて、価値に現在の物品の価値を加算）。
最終的に、両方の選択肢の最大値を取ります。
初期状態
dpTable[0][j] = 0（0個の物品の場合、どの容量でも価値は0）。dpTable[i][0] = 0（バックパックの容量が0の場合、何も詰められず価値は0）。
コード実装（C++）
#include <iostream>
#include <vector>
#include <algorithm>
int solveZeroOneKnapsack(int numItems, int maxCapacity, const std::vector<int>& weights, const std::vector<int>& values) {
// dpTable[i][j]：最初のi個の物品を、容量jで詰めた場合の最大価値
std::vector<std::vector<int>> dpTable(numItems + 1, std::vector<int>(maxCapacity + 1, 0));
for (int itemIdx = 1; itemIdx <= numItems; ++itemIdx) {
for (int capIdx = 1; capIdx <= maxCapacity; ++capIdx) {
if (capIdx < weights[itemIdx]) {
// 容量が足りないため、i番目の物品は選択できない
dpTable[itemIdx][capIdx] = dpTable[itemIdx - 1][capIdx];
} else {
// 選択しない場合と選択する場合の価値を比較し、最大値を取る
dpTable[itemIdx][capIdx] = std::max(dpTable[itemIdx - 1][capIdx],
dpTable[itemIdx - 1][capIdx - weights[itemIdx]] + values[itemIdx]);
}
}
}
return dpTable[numItems][maxCapacity]; // 答え：numItems個の物品を、容量maxCapacityで詰めた場合の最大価値
}
int main() {
// テストケース：物品数numItems=3, バックパック容量maxCapacity=5
// 物品1：重量1, 価値2；物品2：重量2, 価値3；物品3：重量3, 価値4
int numItems = 3, maxCapacity = 5;
std::vector<int> weights = {0, 1, 2, 3}; // インデックスを1から始めるため、先頭に0を追加
std::vector<int> values = {0, 2, 3, 4};
int maxValue = solveZeroOneKnapsack(numItems, maxCapacity, weights, values);
std::cout << "01バックパックの最大価値: " << maxValue << std::endl; // 出力: 7 (物品2と3を選択)
return 0;
}このコードは理解しやすいですが、二次元配列は O(numItems * maxCapacity) の空間を消費します。もし numItems や maxCapacity が非常に大きい場合（例: 1e4）、メモリ不足になる可能性があります。そのため、実戦では**一次元配列による最適化**が一般的です。
2.2. 一次元配列による最適化（空間計算量O(maxCapacity)）
一次元配列による最適化の核心は「ローリング配列」です。状態遷移式を観察すると、 dpTable[i][j] は dpTable[i-1][...]（前の層の状態）のみに依存することがわかります。したがって、二次元配列を一次元配列 dpTable[j] で置き換えることができます。ただし、**容量のループは後ろから前に走査する必要があります**（同じ物品を複数回選択するのを防ぐため）。
状態定義
dpTable[j]：現在のバックパック容量 j での最大価値（二次元配列の dpTable[i][j] と等価）。
状態遷移
dpTable[j] = std::max(dpTable[j], dpTable[j - weights[itemIdx]] + values[itemIdx]) （j >= weights[itemIdx] の場合）。
重要：容量は後ろから前にループする
前からループすると（例: j を1から maxCapacity まで）、同じ物品が複数回選択されてしまい、01バックパックの「各物品は1回のみ選択可能」というルールに反します。後ろからループすることで、各物品が1回しか考慮されないことを保証できます。
コード実装（C++）
#include <iostream>
#include <vector>
#include <algorithm>
int solveZeroOneKnapsackOptimized(int numItems, int maxCapacity, const std::vector<int>& weights, const std::vector<int>& values) {
std::vector<int> dpTable(maxCapacity + 1, 0); // 一次元dp配列、初期値は全て0
for (int itemIdx = 1; itemIdx <= numItems; ++itemIdx) {
// 容量を後ろからループし、重複選択を避ける
for (int capIdx = maxCapacity; capIdx >= weights[itemIdx]; --capIdx) {
dpTable[capIdx] = std::max(dpTable[capIdx], dpTable[capIdx - weights[itemIdx]] + values[itemIdx]);
}
}
return dpTable[maxCapacity];
}
int main() {
int numItems = 3, maxCapacity = 5;
std::vector<int> weights = {0, 1, 2, 3};
std::vector<int> values = {0, 2, 3, 4};
int maxValue = solveZeroOneKnapsackOptimized(numItems, maxCapacity, weights, values);
std::cout << "最適化版01バックパックの最大価値: " << maxValue << std::endl; // 出力: 7
return 0;
}3. クラシックなバリエーション：完全バックパック（各物品は無制限に選択可能）
完全バックパックは01バックパックと異なり、「各物品を無制限に選択できる」という点が異なります。
3.1. 核心思想
01バックパックとの主な違いは、容量のループの方向です。
- 01バックパック：容量は後ろから前にループ（重複選択を避ける）。
- 完全バックパック：容量は前から後にループ（重複選択を許可）。
なぜ前からループするかというと、完全バックパックは同じ物品を複数回選択できるため、 dpTable[j - weights[itemIdx]] はすでに現在の物品を1回選択した後の状態を指しており、これに values[itemIdx] を加えることで、さらに1回選択した状態を表現できるからです。
3.2. コード実装（C++）
#include <iostream>
#include <vector>
#include <algorithm>
int solveCompleteKnapsack(int numItems, int maxCapacity, const std::vector<int>& weights, const std::vector<int>& values) {
std::vector<int> dpTable(maxCapacity + 1, 0);
for (int itemIdx = 1; itemIdx <= numItems; ++itemIdx) {
// 容量を前からループし、重複選択を許可
for (int capIdx = weights[itemIdx]; capIdx <= maxCapacity; ++capIdx) {
dpTable[capIdx] = std::max(dpTable[capIdx], dpTable[capIdx - weights[itemIdx]] + values[itemIdx]);
}
}
return dpTable[maxCapacity];
}
int main() {
// テストケース：物品数numItems=2, バックパック容量maxCapacity=5
// 物品1：重量1, 価値2；物品2：重量2, 価値3
int numItems = 2, maxCapacity = 5;
std::vector<int> weights = {0, 1, 2};
std::vector<int> values = {0, 2, 3};
int maxValue = solveCompleteKnapsack(numItems, maxCapacity, weights, values);
std::cout << "完全バックパックの最大価値: " << maxValue << std::endl; // 出力: 10 (物品1を5つ選択)
return 0;
}4. 進化版バリエーション：多重バックパック（各物品は指定回数まで選択可能）
多重バックパックは「各物品を最大 counts[i] 回まで選択可能」という制約を持っています。
4.1. 朴素な分割法（理解用）
最も単純な方法は、 counts[i] 個の同じ物品に分割し、通常の01バックパックで解くことです。
コード実装（C++）
#include <iostream>
#include <vector>
#include <algorithm>
int solveMultipleKnapsackNaive(int numItems, int maxCapacity, const std::vector<int>& weights, const std::vector<int>& values, const std::vector<int>& counts) {
std::vector<int> newWeights, newValues;
for (int i = 1; i <= numItems; ++i) {
for (int j = 1; j <= counts[i]; ++j) {
newWeights.push_back(weights[i]);
newValues.push_back(values[i]);
}
}
// 01バックパックで解く
std::vector<int> dpTable(maxCapacity + 1, 0);
int m = newWeights.size();
for (int i = 0; i < m; ++i) {
for (int j = maxCapacity; j >= newWeights[i]; --j) {
dpTable[j] = std::max(dpTable[j], dpTable[j - newWeights[i]] + newValues[i]);
}
}
return dpTable[maxCapacity];
}
int main() {
// テストケース：物品数numItems=2, バックパック容量maxCapacity=5
// 物品1：重量1, 価値2, 最大3回；物品2：重量2, 価値3, 最大1回
int numItems = 2, maxCapacity = 5;
std::vector<int> weights = {0, 1, 2};
std::vector<int> values = {0, 2, 3};
std::vector<int> counts = {0, 3, 1};
int maxValue = solveMultipleKnapsackNaive(numItems, maxCapacity, weights, values, counts);
std::cout << "朴素版多重バックパックの最大価値: " << maxValue << std::endl; // 出力: 9
return 0;
}この方法はシンプルですが、効率が悪いです。もし counts[i] が1e5程度の場合、分割後の物品数が爆発的に増え、計算時間とメモリが不足します。
4.2. 二進分割法（実戦でよく使われる）
二進分割法の核心は、任意の整数 k を2のべき乗の和（例: 7 = 1 + 2 + 4, 10 = 1 + 2 + 4 + 3）に分割できるという性質を利用することです。これにより、分割後の物品数を k 個から log2(k) 個に大幅に削減できます。
例えば、 counts[i]=5 の場合、1, 2, 2（1+2=3, 残り2）のように分割します。分割後の各「合成物品」は、1回、2回、2回選択することを意味し、0~5回の選択をすべてカバーできます。
コード実装（C++）
#include <iostream>
#include <vector>
#include <algorithm>
int solveMultipleKnapsackBinary(int numItems, int maxCapacity, const std::vector<int>& weights, const std::vector<int>& values, const std::vector<int>& counts) {
std::vector<int> newWeights, newValues;
for (int i = 1; i <= numItems; ++i) {
int remaining = counts[i];
// 二進分割: 1, 2, 4, ...
for (int j = 1; j <= remaining; j *= 2) {
newWeights.push_back(weights[i] * j);
newValues.push_back(values[i] * j);
remaining -= j;
}
// 残りの数量を処理
if (remaining > 0) {
newWeights.push_back(weights[i] * remaining);
newValues.push_back(values[i] * remaining);
}
}
// 01バックパックで解く
std::vector<int> dpTable(maxCapacity + 1, 0);
int m = newWeights.size();
for (int i = 0; i < m; ++i) {
for (int j = maxCapacity; j >= newWeights[i]; --j) {
dpTable[j] = std::max(dpTable[j], dpTable[j - newWeights[i]] + newValues[i]);
}
}
return dpTable[maxCapacity];
}
int main() {
int numItems = 2, maxCapacity = 5;
std::vector<int> weights = {0, 1, 2};
std::vector<int> values = {0, 2, 3};
std::vector<int> counts = {0, 3, 1};
int maxValue = solveMultipleKnapsackBinary(numItems, maxCapacity, weights, values, counts);
std::cout << "二進分割版多重バックパックの最大価値: " << maxValue << std::endl; // 出力: 9
return 0;
}5. その他の一般的なバックパックバリエーション（概要）
他にも2つの高頻度のバリエーションがあります。
5.1. 混合バックパック（01 + 完全 + 多重）
各物品のタイプ（01, 完全, 多重）を判断し、対応する方法で処理します。
- 01バックパック：容量は後ろから前にループ。
- 完全バックパック：容量は前から後にループ。
- 多重バックパック：二進分割後、01バックパックとして処理。
5.2. グループバックパック（各グループから最大1つ選択）
物品をいくつかのグループに分け、各グループから最大1つの物品を選択します。
コアロジック
// グループバックパックのコアコード
for (int groupIdx = 1; groupIdx <= groupCount; ++groupIdx) { // 各グループをループ
for (int capIdx = maxCapacity; capIdx >= 0; --capIdx) { // 容量を後ろからループ
for (const auto& item : groups[groupIdx]) { // グループ内の各物品をループ
if (capIdx >= item.weight) {
dpTable[capIdx] = std::max(dpTable[capIdx], dpTable[capIdx - item.weight] + item.value);
}
}
}
}6. バックパックDPの一般的な落とし穴と最適化
- 01バックパックのループ順序：必ず後ろから前にループし、そうでないと完全バックパックになってしまう。
- 物品のインデックス：1から始めることを推奨（境界処理が簡単になる）。
- 二進分割：残りの数量を忘れずに処理する（例: k=5の場合、1+2+2と分割する）。
一般的な最適化テクニック：
- 空間最適化：すべてのバックパック問題を一次元配列に最適化できる（ローリング配列の核心）。
- 枝刈り：物品の重量がバックパック容量を超える場合は、スキップする。
- 価値最適化：物品の価値が0の場合は、スキップする（意味がない）。