ナップサック問題の概要

基本的な解決策

方法一：二次元配列を使用した01ナップサック問題

1. dp配列の定義
2. 再帰式の決定
3. dp配列の初期化
4. ループ処理

import java.util.*;
public class ItemManager {
    public static void main(String[] args) {
        Scanner reader = new Scanner(System.in);
        int itemCount = reader.nextInt();
        int capacity = reader.nextInt();
        int[] itemWeights = new int[itemCount];
        for (int i = 0; i < itemCount; i++) {
            itemWeights[i] = reader.nextInt();
        }
        int[] itemValues = new int[itemCount];
        for (int i = 0; i < itemCount; i++) {
            itemValues[i] = reader.nextInt();
        }
        int[][] dpTable = new int[itemCount][capacity + 1];
        for (int j = itemWeights[0]; j <= capacity; j++) {
            dpTable[0][j] = itemValues[0];
        }
        for (int i = 1; i < itemCount; i++) {
            for (int j = 1; j <= capacity; j++) {
                if (j < itemWeights[i]) {
                    dpTable[i][j] = dpTable[i - 1][j];
                } else {
                    dpTable[i][j] = Math.max(dpTable[i - 1][j], dpTable[i - 1][j - itemWeights[i]] + itemValues[i]);
                }
            }
        }
        System.out.println(dpTable[itemCount - 1][capacity]);
    }
}

方法二：スクロール配列を使用した01ナップサック問題

1. dp配列の定義
2. 再帰式の決定
3. 初期化処理
4. ループ順序

import java.util.*;
public class ScrollArraySolution {
    public static void main(String[] args) {
        Scanner reader = new Scanner(System.in);
        int itemCount = reader.nextInt();
        int capacity = reader.nextInt();
        int[] itemWeights = new int[itemCount];
        for (int i = 0; i < itemCount; i++) {
            itemWeights[i] = reader.nextInt();
        }
        int[] itemValues = new int[itemCount];
        for (int i = 0; i < itemCount; i++) {
            itemValues[i] = reader.nextInt();
        }
        int[] dp = new int[capacity + 1];
        for (int i = 0; i < itemCount; i++) {
            for (int j = capacity; j >= itemWeights[i]; j--) {
                dp[j] = Math.max(dp[j], dp[j - itemWeights[i]] + itemValues[i]);
            }
        }
        System.out.println(dp[capacity]);
    }
}

問題698. k個の等しい部分に分割する

class SubsetPartition {
    private static int[] usedIndices;
    public boolean canDivideIntoKSubsets(int[] nums, int k) {
        usedIndices = new int[nums.length];
        Arrays.sort(nums);
        int totalSum = 0;
        for (int num : nums) {
            totalSum += num;
        }
        if (totalSum % k != 0 || nums[nums.length - 1] > totalSum / k) return false;
        return divideGroups(nums, nums.length - 1, totalSum / k, 0, k);
    }

    private boolean divideGroups(int[] nums, int start, int target, int currentSum, int remainingGroups) {
        if (remainingGroups == 1) return true;
        if (currentSum == target) return divideGroups(nums, nums.length - 1, target, 0, remainingGroups - 1);
        for (int i = start; i >= 0; i--) {
            if (usedIndices[i] == 1 || currentSum + nums[i] > target) continue;
            usedIndices[i] = 1;
            if (divideGroups(nums, i - 1, target, currentSum + nums[i], remainingGroups)) return true;
            usedIndices[i] = 0;
            while (i > 0 && nums[i - 1] == nums[i]) i--;
        }
        return false;
    }
}

問題416. 等和子集合への分割

class EqualSubsetPartition {
    public boolean canPartition(int[] nums) {
        int totalSum = 0;
        for (int num : nums) {
            totalSum += num;
        }
        if (totalSum % 2 != 0) return false;
        int target = totalSum / 2;
        int[] dp = new int[target + 1];
        for (int i = 0; i < nums.length; i++) {
            for (int j = target; j >= nums[i]; j--) {
                dp[j] = Math.max(dp[j], dp[j - nums[i]] + nums[i]);
            }
            if (dp[target] == target) return true;
        }
        return dp[target] == target;
    }
}