ナップサック問題は、有限の容量を持つバッグにどの物品を詰めるかを最適化する古典的なアルゴリズム問題です。特に0/1ナップサック問題は、各物品をバッグに入れるか入れないかの二択しかない場合を指します。
問題設定：
3つの物品があります：
- 物品A：価値1000、重量1kg
- 物品B：価値2000、重量4kg
- 物品C：価値1500、重量3kg
バッグの容量は4kgで、この中に詰められる物品の最大価値はいくらでしょうか？
動的計画法による解法：
動的計画法は、問題を小さな部分問題に分割し、それらの解を組み合わせて全体の解を構築する手法です。ナップサック問題では、各物品を順に考慮していき、各容量における最適解を段階的に計算していきます。
まず、最初の物品Aのみを考慮した場合：
- バッグ容量0kg: 最大価値0
- バッグ容量1kg: 最大価値1000
- バッグ容量2kg: 最大価値1000
- バッグ容量3kg: 最大価値1000
- バッグ容量4kg: 最大価値1000
次に、物品AとBを考慮します：
- 容量が0-3kgの場合：物品Bは入れられないため、依然としてAのみの策略を使用
- 容量が4kgの場合：物品Bを入れるかどうかの選択肢があります
- 物品Bを入れる場合：
- 残り容量 = 4kg - 4kg = 0kg
- 価値 = 物品Bの価値(2000) + 残り容量での最適解(0) = 2000
- 物品Bを入れない場合：
- 価値 = 物品Aのみの場合の価値(1000)
両者を比較し、価値が高い方を選択すると、2000が最適解となります。
同様の方法で物品Cを考慮していき、最終的な最適解を導き出します。
以下はJavaによる実装例です：
package algorithm;
public class Knapsack {
// 0/1ナップサック問題の解法
public static void main(String[] args) {
int[] values = {0, 1000, 2000, 1500}; // 物品の価値（0番目はダミー）
int[] weights = {0, 1, 4, 3}; // 物品の重量（0番目はダミー）
int capacity = 4; // バッグの容量
System.out.println("バッグに入れられる最大価値: " + maxKnapsackValue(values, weights, capacity));
}
public static int maxKnapsackValue(int[] values, int[] weights, int capacity) {
int n = values.length;
int[][] dp = new int[n][capacity + 1]; // dp[i][j]: 最初のi個の物品で容量jの場合の最大価値
// 基本ケース：最初の物品のみ
for (int j = 0; j <= capacity; j++) {
if (weights[0] <= j) {
dp[0][j] = values[0];
}
}
// 動的計画法による表の構築
for (int i = 1; i < n; i++) {
for (int j = 0; j <= capacity; j++) {
if (weights[i] > j) {
// 現在の物品を入れられない場合
dp[i][j] = dp[i-1][j];
} else {
// 現在の物品を入れる場合と入れない場合の価値を比較
dp[i][j] = Math.max(dp[i-1][j], values[i] + dp[i-1][j - weights[i]]);
}
}
}
// 結果の表示
for (int i = 0; i < n; i++) {
for (int j = 0; j <= capacity; j++) {
System.out.print(dp[i][j] + " ");
}
System.out.println();
}
return dp[n-1][capacity];
}
}
次に、どの物品が選択されたかを特定するコードです：
package algorithm;
public class KnapsackSolution {
public static void main(String[] args) {
int[] values = {0, 1000, 2000, 1500};
int[] weights = {0, 1, 4, 3};
int capacity = 4;
SolutionResult result = findOptimalItems(values, weights, capacity);
System.out.println("最大価値: " + result.maxValue);
System.out.println("選択された物品:");
for (int item : result.selectedItems) {
System.out.println("物品" + item + "（価値: " + values[item] + ", 重量: " + weights[item] + "）");
}
}
public static SolutionResult findOptimalItems(int[] values, int[] weights, int capacity) {
int n = values.length;
int[][] dp = new int[n][capacity + 1];
boolean[][] selected = new boolean[n][capacity + 1];
// 基本ケース
for (int j = 0; j <= capacity; j++) {
if (weights[0] <= j) {
dp[0][j] = values[0];
selected[0][j] = true;
}
}
// 動的計画法による表の構築
for (int i = 1; i < n; i++) {
for (int j = 0; j <= capacity; j++) {
if (weights[i] > j) {
dp[i][j] = dp[i-1][j];
} else {
if (dp[i-1][j] > values[i] + dp[i-1][j - weights[i]]) {
dp[i][j] = dp[i-1][j];
} else {
dp[i][j] = values[i] + dp[i-1][j - weights[i]];
selected[i][j] = true;
}
}
}
}
// 選択された物品の特定
List<Integer> items = new ArrayList<>();
int remainingCapacity = capacity;
for (int i = n-1; i > 0; i--) {
if (selected[i][remainingCapacity]) {
items.add(i);
remainingCapacity -= weights[i];
}
}
return new SolutionResult(dp[n-1][capacity], items);
}
static class SolutionResult {
int maxValue;
List<Integer> selectedItems;
SolutionResult(int maxValue, List<Integer> selectedItems) {
this.maxValue = maxValue;
this.selectedItems = selectedItems;
}
}
}
この実装では、動的計画法を使ってナップサック問題を効率的に解いています。最初のコードは最大価値を計算し、2つ目のコードではどの物品が選択されたかも特定しています。時間計算量はO(nW)で、nは物品の数、Wはバッグの容量です。