ジャバを使用してナップサック問題を解決する方法

2年 ago
桜, 春樹
1 minute

ナップサック問題は、動的計画法で解くことができる、組合せ最適化問題の古典である。以下に、ナップサック問題をJavaで解く例を示す。

public class KnapsackProblem {
    public static int knapSack(int capacity, int[] weights, int[] values, int n) {
        int[][] dp = new int[n + 1][capacity + 1];

        for (int i = 0; i <= n; i++) {
            for (int j = 0; j <= capacity; j++) {
                if (i == 0 || j == 0) {
                    dp[i][j] = 0;
                } else if (weights[i - 1] <= j) {
                    dp[i][j] = Math.max(values[i - 1] + dp[i - 1][j - weights[i - 1]], dp[i - 1][j]);
                } else {
                    dp[i][j] = dp[i - 1][j];
                }
            }
        }

        return dp[n][capacity];
    }

    public static void main(String[] args) {
        int capacity = 10;
        int[] weights = {2, 3, 4, 5};
        int[] values = {3, 4, 5, 6};
        int n = weights.length;
        int maxValue = knapSack(capacity, weights, values, n);
        System.out.println("背包能装下的最大价值为: " + maxValue);
    }
}

上記のサンプルでは、ナップサック法によってナップサック問題が解かれています。バックの容量、アイテムの重量配列、アイテムの価値配列、アイテムの数を引数として求め、バックに収まる最大の価値を返します。

mainメソッドでは容量10のナップサックを定義し、アイテムの重量配列を{2, 3, 4, 5}に、アイテムの価値配列を{3, 4, 5, 6}に、アイテム数を4に設定しています。その後、ナップサックが保持できる最大の価値を求めるknapSackメソッドを呼び出し、その結果を出力します。

上記のコードを実行すると、出力される結果は以下のようになります。

背包能装下的最大价值为: 10
bannerAds