Knapsack Problem (Çanta Problemi)

Problem Təsviri

Müəyyən tutumu olan bir çantanız var. Hər birinin dəyəri və çəkisi olan əşyalar verilmişdir. Çantanın tutumunu aşmadan maksimum dəyəri əldə edəcək əşyaları seçin.

0/1 Knapsack: Hər əşyadan ya götürürsünüz, ya da götürmürsünüz (hissə-hissə olmur).

Məsələn:

• Tutum: 50
• Əşyalar:
  • value : 60, çəki: 10
  • value: 100, çəki: 20
  • value: 120, çəki: 30
• Maksimum dəyər: 220 (əşya 2 və 3)

Recurrence Relation:

dp[i][w] = max(
    dp[i-1][w],                    // don't take item i
    dp[i-1][w-weight[i]] + value[i] // take item i
)

Müxtəlif Yanaşmalar

1. Sadə Rekursiya (Naive Approach)

Koda bax

public class KnapsackNaive {
    
    public static int knapsack(int[] weights, int[] values, int capacity) {
        return knapsackHelper(weights, values, capacity, weights.length);
    }
    
    private static int knapsackHelper(int[] weights, int[] values, 
                                      int capacity, int n) {
        // Base cases
        if (n == 0 || capacity == 0) {
            return 0;
        }
        
        // If weight of nth item is more than capacity, can't include it
        if (weights[n - 1] > capacity) {
            return knapsackHelper(weights, values, capacity, n - 1);
        }
        
        // Return maximum of:
        // 1. nth item included
        // 2. not included
        int include = values[n - 1] + 
                     knapsackHelper(weights, values, 
                                   capacity - weights[n - 1], n - 1);
        int exclude = knapsackHelper(weights, values, capacity, n - 1);
        
        return Math.max(include, exclude);
    }
    
    public static void main(String[] args) {
        System.out.println("0/1 Knapsack (Naive Recursion):");
        
        int[] weights = {10, 20, 30};
        int[] values = {60, 100, 120};
        int capacity = 50;
        
        System.out.println("Çəkilər: [10, 20, 30]");
        System.out.println("Dəyərlər: [60, 100, 120]");
        System.out.println("Tutum: " + capacity);
        System.out.println("Maksimum dəyər: " + knapsack(weights, values, capacity));
        
        // Performance test
        int[] weights2 = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
        int[] values2 = {10, 20, 30, 40, 50, 60, 70, 80, 90, 100};
        
        long startTime = System.currentTimeMillis();
        int result = knapsack(weights2, values2, 20);
        long endTime = System.currentTimeMillis();
        
        System.out.println("\n10 əşya, tutum 20");
        System.out.println("Maksimum dəyər: " + result);
        System.out.println("Vaxt: " + (endTime - startTime) + " ms");
    }
}

Mürəkkəblik:

• Time Complexity: O(2^n) - Eksponensial
• Space Complexity: O(n) - Rekursiya stack-i

Problemlər:

• Çox yavaş çox əşya üçün
• Eyni alt-problemlər dəfələrlə hesablanır

2. Memoization (Top-Down DP)

Koda bax

import java.util.HashMap;
import java.util.Map;

public class KnapsackMemoization {
    
    // Using 2D array for memoization
    public static int knapsack(int[] weights, int[] values, int capacity) {
        int n = weights.length;
        int[][] memo = new int[n + 1][capacity + 1];
        
        // Initialize with -1 (not computed)
        for (int i = 0; i <= n; i++) {
            for (int j = 0; j <= capacity; j++) {
                memo[i][j] = -1;
            }
        }
        
        return knapsackHelper(weights, values, capacity, n, memo);
    }
    
    private static int knapsackHelper(int[] weights, int[] values, 
                                      int capacity, int n, int[][] memo) {
        // Base cases
        if (n == 0 || capacity == 0) {
            return 0;
        }
        
        // Check if already computed
        if (memo[n][capacity] != -1) {
            return memo[n][capacity];
        }
        
        // If weight exceeds capacity, can't include
        if (weights[n - 1] > capacity) {
            memo[n][capacity] = knapsackHelper(weights, values, 
                                              capacity, n - 1, memo);
        } else {
            // Max of include or exclude
            int include = values[n - 1] + 
                         knapsackHelper(weights, values, 
                                       capacity - weights[n - 1], n - 1, memo);
            int exclude = knapsackHelper(weights, values, capacity, n - 1, memo);
            
            memo[n][capacity] = Math.max(include, exclude);
        }
        
        return memo[n][capacity];
    }
    
    // Alternative: Using HashMap with string key
    private static Map<String, Integer> memoMap = new HashMap<>();
    
    public static int knapsackMap(int[] weights, int[] values, int capacity) {
        memoMap.clear();
        return knapsackHelperMap(weights, values, capacity, weights.length);
    }
    
    private static int knapsackHelperMap(int[] weights, int[] values, 
                                         int capacity, int n) {
        if (n == 0 || capacity == 0) return 0;
        
        String key = n + "," + capacity;
        if (memoMap.containsKey(key)) {
            return memoMap.get(key);
        }
        
        int result;
        if (weights[n - 1] > capacity) {
            result = knapsackHelperMap(weights, values, capacity, n - 1);
        } else {
            int include = values[n - 1] + 
                         knapsackHelperMap(weights, values, 
                                          capacity - weights[n - 1], n - 1);
            int exclude = knapsackHelperMap(weights, values, capacity, n - 1);
            result = Math.max(include, exclude);
        }
        
        memoMap.put(key, result);
        return result;
    }
    
    public static void main(String[] args) {
        System.out.println("0/1 Knapsack (Memoization):");
        
        int[] weights = {10, 20, 30};
        int[] values = {60, 100, 120};
        int capacity = 50;
        
        System.out.println("Çəkilər: [10, 20, 30]");
        System.out.println("Dəyərlər: [60, 100, 120]");
        System.out.println("Tutum: " + capacity);
        System.out.println("Maksimum dəyər: " + knapsack(weights, values, capacity));
        
        // Performance test
        int[] weights2 = new int[100];
        int[] values2 = new int[100];
        for (int i = 0; i < 100; i++) {
            weights2[i] = i + 1;
            values2[i] = (i + 1) * 10;
        }
        
        long startTime = System.currentTimeMillis();
        int result = knapsack(weights2, values2, 500);
        long endTime = System.currentTimeMillis();
        
        System.out.println("\n100 əşya, tutum 500");
        System.out.println("Maksimum dəyər: " + result);
        System.out.println("Vaxt: " + (endTime - startTime) + " ms");
    }
}

Mürəkkəblik:

• Time Complexity: O(n * W) - n: əşya sayı, W: tutum
• Space Complexity: O(n * W) - Memo table və rekursiya stack-i

3. Tabulation (Bottom-Up DP)

Koda bax

public class KnapsackTabulation {
    
    public static int knapsack(int[] weights, int[] values, int capacity) {
        int n = weights.length;
        
        // Create DP table
        int[][] dp = new int[n + 1][capacity + 1];
        
        // Base case: dp[0][w] = 0 and dp[i][0] = 0 (already initialized)
        
        // Fill table bottom-up
        for (int i = 1; i <= n; i++) {
            for (int w = 1; w <= capacity; w++) {
                // If current item can fit
                if (weights[i - 1] <= w) {
                    // Max of include or exclude
                    dp[i][w] = Math.max(
                        dp[i - 1][w],                              // exclude
                        dp[i - 1][w - weights[i - 1]] + values[i - 1] // include
                    );
                } else {
                    // Can't include, take previous value
                    dp[i][w] = dp[i - 1][w];
                }
            }
        }
        
        return dp[n][capacity];
    }
    
    // Method to print DP table
    public static void printDPTable(int[] weights, int[] values, int capacity) {
        int n = weights.length;
        int[][] dp = new int[n + 1][capacity + 1];
        
        for (int i = 1; i <= n; i++) {
            for (int w = 1; w <= capacity; w++) {
                if (weights[i - 1] <= w) {
                    dp[i][w] = Math.max(
                        dp[i - 1][w],
                        dp[i - 1][w - weights[i - 1]] + values[i - 1]
                    );
                } else {
                    dp[i][w] = dp[i - 1][w];
                }
            }
        }
        
        System.out.println("\nDP Table:");
        System.out.print("W\\I\t");
        for (int i = 0; i <= n; i++) {
            System.out.print(i + "\t");
        }
        System.out.println();
        
        for (int w = 0; w <= capacity; w++) {
            System.out.print(w + "\t");
            for (int i = 0; i <= n; i++) {
                System.out.print(dp[i][w] + "\t");
            }
            System.out.println();
        }
    }
    
    public static void main(String[] args) {
        System.out.println("0/1 Knapsack (Tabulation):");
        
        int[] weights = {10, 20, 30};
        int[] values = {60, 100, 120};
        int capacity = 50;
        
        System.out.println("Çəkilər: [10, 20, 30]");
        System.out.println("Dəyərlər: [60, 100, 120]");
        System.out.println("Tutum: " + capacity);
        System.out.println("Maksimum dəyər: " + knapsack(weights, values, capacity));
        
        printDPTable(weights, values, capacity);
        
        // Performance test
        long startTime = System.currentTimeMillis();
        int result = knapsack(weights, values, capacity);
        long endTime = System.currentTimeMillis();
        
        System.out.println("\nVaxt: " + (endTime - startTime) + " ms");
    }
}

Mürəkkəblik:

• Time Complexity: O(n * W)
• Space Complexity: O(n * W) - DP table üçün

4. Space Optimized (O(W) Space)

Koda bax

public class KnapsackOptimized {
    
    // Using two 1D arrays
    public static int knapsack(int[] weights, int[] values, int capacity) {
        int n = weights.length;
        
        // Use only two rows
        int[] prev = new int[capacity + 1];
        int[] curr = new int[capacity + 1];
        
        for (int i = 1; i <= n; i++) {
            for (int w = 1; w <= capacity; w++) {
                if (weights[i - 1] <= w) {
                    curr[w] = Math.max(
                        prev[w],
                        prev[w - weights[i - 1]] + values[i - 1]
                    );
                } else {
                    curr[w] = prev[w];
                }
            }
            
            // Swap arrays
            int[] temp = prev;
            prev = curr;
            curr = temp;
        }
        
        return prev[capacity];
    }
    
    // Ultra optimized: single array (traverse backwards)
    public static int knapsackSingleArray(int[] weights, int[] values, int capacity) {
        int n = weights.length;
        int[] dp = new int[capacity + 1];
        
        for (int i = 0; i < n; i++) {
            // Traverse backwards to avoid using updated values
            for (int w = capacity; w >= weights[i]; w--) {
                dp[w] = Math.max(
                    dp[w],
                    dp[w - weights[i]] + values[i]
                );
            }
        }
        
        return dp[capacity];
    }
    
    public static void main(String[] args) {
        System.out.println("0/1 Knapsack (Space Optimized):");
        
        int[] weights = {10, 20, 30};
        int[] values = {60, 100, 120};
        int capacity = 50;
        
        System.out.println("Çəkilər: [10, 20, 30]");
        System.out.println("Dəyərlər: [60, 100, 120]");
        System.out.println("Tutum: " + capacity);
        System.out.println("Maksimum dəyər: " + knapsack(weights, values, capacity));
        System.out.println("Single array: " + knapsackSingleArray(weights, values, capacity));
        
        // Performance test with large input
        int[] largeWeights = new int[1000];
        int[] largeValues = new int[1000];
        for (int i = 0; i < 1000; i++) {
            largeWeights[i] = (i % 50) + 1;
            largeValues[i] = (i % 100) + 1;
        }
        
        long startTime = System.currentTimeMillis();
        int result = knapsackSingleArray(largeWeights, largeValues, 500);
        long endTime = System.currentTimeMillis();
        
        System.out.println("\n1000 əşya, tutum 500");
        System.out.println("Maksimum dəyər: " + result);
        System.out.println("Vaxt: " + (endTime - startTime) + " ms");
    }
}

Mürəkkəblik:

• Time Complexity: O(n * W)
• Space Complexity: O(W) - Yalnız bir array

5. Item Tracking (Hansı Əşyalar Seçildi)

Koda bax

import java.util.ArrayList;
import java.util.List;

public class KnapsackWithItems {
    
    public static class Result {
        int maxValue;
        List<Integer> items;
        int totalWeight;
        
        Result(int maxValue, List<Integer> items, int totalWeight) {
            this.maxValue = maxValue;
            this.items = items;
            this.totalWeight = totalWeight;
        }
    }
    
    public static Result knapsackWithItems(int[] weights, int[] values, int capacity) {
        int n = weights.length;
        int[][] dp = new int[n + 1][capacity + 1];
        
        // Fill DP table
        for (int i = 1; i <= n; i++) {
            for (int w = 1; w <= capacity; w++) {
                if (weights[i - 1] <= w) {
                    dp[i][w] = Math.max(
                        dp[i - 1][w],
                        dp[i - 1][w - weights[i - 1]] + values[i - 1]
                    );
                } else {
                    dp[i][w] = dp[i - 1][w];
                }
            }
        }
        
        // Backtrack to find items
        List<Integer> selectedItems = new ArrayList<>();
        int w = capacity;
        int totalWeight = 0;
        
        for (int i = n; i > 0 && w > 0; i--) {
            // If value comes from including item i
            if (dp[i][w] != dp[i - 1][w]) {
                selectedItems.add(i - 1); // Add item index
                totalWeight += weights[i - 1];
                w -= weights[i - 1];
            }
        }
        
        return new Result(dp[n][capacity], selectedItems, totalWeight);
    }
    
    public static void main(String[] args) {
        System.out.println("0/1 Knapsack with Item Tracking:");
        
        int[] weights = {10, 20, 30};
        int[] values = {60, 100, 120};
        int capacity = 50;
        
        System.out.println("Çəkilər: [10, 20, 30]");
        System.out.println("Dəyərlər: [60, 100, 120]");
        System.out.println("Tutum: " + capacity);
        
        Result result = knapsackWithItems(weights, values, capacity);
        
        System.out.println("\nMaksimum dəyər: " + result.maxValue);
        System.out.println("Seçilmiş əşyalar (index): " + result.items);
        System.out.println("Ümumi çəki: " + result.totalWeight);
        
        System.out.println("\nÆşya təfərrüatları:");
        for (int idx : result.items) {
            System.out.println("Əşya " + idx + ": çəki=" + 
                             weights[idx] + ", dəyər=" + values[idx]);
        }
    }
}

Mürəkkəblik:

• Time Complexity: O(n * W)
• Space Complexity: O(n * W) - Backtracking üçün tam DP table lazımdır

Variantlar

Koda bax

public class KnapsackVariants {
    
    // 1. Unbounded Knapsack (hər əşyadan istənilən sayda götürə bilərsiniz)
    public static int unboundedKnapsack(int[] weights, int[] values, int capacity) {
        int[] dp = new int[capacity + 1];
        
        for (int w = 1; w <= capacity; w++) {
            for (int i = 0; i < weights.length; i++) {
                if (weights[i] <= w) {
                    dp[w] = Math.max(dp[w], dp[w - weights[i]] + values[i]);
                }
            }
        }
        
        return dp[capacity];
    }
    
    // 2. Fractional Knapsack (hissə-hissə götürə bilərsiniz) - Greedy
    public static double fractionalKnapsack(int[] weights, int[] values, int capacity) {
        int n = weights.length;
        
        // Create array of items with value/weight ratio
        Item[] items = new Item[n];
        for (int i = 0; i < n; i++) {
            items[i] = new Item(weights[i], values[i], i);
        }
        
        // Sort by value/weight ratio in descending order
        java.util.Arrays.sort(items, (a, b) -> 
            Double.compare(b.ratio, a.ratio));
        
        double totalValue = 0;
        int remainingCapacity = capacity;
        
        for (Item item : items) {
            if (item.weight <= remainingCapacity) {
                // Take whole item
                totalValue += item.value;
                remainingCapacity -= item.weight;
            } else {
                // Take fraction of item
                totalValue += item.value * ((double) remainingCapacity / item.weight);
                break;
            }
        }
        
        return totalValue;
    }
    
    static class Item {
        int weight, value, index;
        double ratio;
        
        Item(int weight, int value, int index) {
            this.weight = weight;
            this.value = value;
            this.index = index;
            this.ratio = (double) value / weight;
        }
    }
    
    // 3. Count Subsets with Given Sum
    public static int countSubsets(int[] arr, int sum) {
        int n = arr.length;
        int[][] dp = new int[n + 1][sum + 1];
        
        // Base case: empty subset has sum 0
        for (int i = 0; i <= n; i++) {
            dp[i][0] = 1;
        }
        
        for (int i = 1; i <= n; i++) {
            for (int s = 1; s <= sum; s++) {
                dp[i][s] = dp[i - 1][s]; // exclude
                
                if (arr[i - 1] <= s) {
                    dp[i][s] += dp[i - 1][s - arr[i - 1]]; // include
                }
            }
        }
        
        return dp[n][sum];
    }
    
    // 4. Partition Equal Subset Sum
    public static boolean canPartition(int[] nums) {
        int sum = 0;
        for (int num : nums) {
            sum += num;
        }
        
        // If sum is odd, can't partition equally
        if (sum % 2 != 0) {
            return false;
        }
        
        int target = sum / 2;
        boolean[] dp = new boolean[target + 1];
        dp[0] = true;
        
        for (int num : nums) {
            for (int s = target; s >= num; s--) {
                dp[s] = dp[s] || dp[s - num];
            }
        }
        
        return dp[target];
    }
    
    // 5. Target Sum (LeetCode 494)
    public static int findTargetSumWays(int[] nums, int target) {
        int sum = 0;
        for (int num : nums) {
            sum += num;
        }
        
        // Check if solution is possible
        if (Math.abs(target) > sum || (sum + target) % 2 != 0) {
            return 0;
        }
        
        int subsetSum = (sum + target) / 2;
        return countSubsets(nums, subsetSum);
    }
    
    public static void main(String[] args) {
        System.out.println("Knapsack Variants:\n");
        
        int[] weights = {10, 20, 30};
        int[] values = {60, 100, 120};
        int capacity = 50;
        
        System.out.println("1. Unbounded Knapsack:");
        System.out.println("Maksimum dəyər: " + 
            unboundedKnapsack(weights, values, capacity));
        
        System.out.println("\n2. Fractional Knapsack:");
        System.out.println("Maksimum dəyər: " + 
            fractionalKnapsack(weights, values, capacity));
        
        System.out.println("\n3. Count Subsets with Sum:");
        int[] arr = {1, 2, 3, 3};
        System.out.println("Array: [1, 2, 3, 3], Sum: 6");
        System.out.println("Count: " + countSubsets(arr, 6));
        
        System.out.println("\n4. Partition Equal Subset Sum:");
        int[] nums = {1, 5, 11, 5};
        System.out.println("Array: [1, 5, 11, 5]");
        System.out.println("Can partition: " + canPartition(nums));
        
        System.out.println("\n5. Target Sum:");
        int[] nums2 = {1, 1, 1, 1, 1};
        System.out.println("Array: [1, 1, 1, 1, 1], Target: 3");
        System.out.println("Ways: " + findTargetSumWays(nums2, 3));
    }
}

Performance Müqayisəsi

Koda bax

public class KnapsackComparison {
    
    public static void comparePerformance() {
        int[][] testCases = {
            {10, 5},    // 10 items, capacity 5
            {20, 10},   // 20 items, capacity 10
            {50, 25},   // 50 items, capacity 25
            {100, 50},  // 100 items, capacity 50
            {200, 100}  // 200 items, capacity 100
        };
        
        System.out.println("Performance Müqayisəsi:");
        System.out.println("Items\tCap\tNaive\t\tMemo\t\tTabulation\tOptimized");
        
        for (int[] test : testCases) {
            int n = test[0];
            int capacity = test[1];
            
            int[] weights = new int[n];
            int[] values = new int[n];
            for (int i = 0; i < n; i++) {
                weights[i] = (i % 10) + 1;
                values[i] = (i % 20) + 1;
            }
            
            System.out.print(n + "\t" + capacity + "\t");
            
            // Naive (only for small n)
            if (n <= 20) {
                long start = System.nanoTime();
                KnapsackNaive.knapsack(weights, values, capacity);
                long end = System.nanoTime();
                System.out.print((end - start) / 1000 + "μs\t\t");
            } else {
                System.out.print("Too slow\t");
            }
            
            // Memoization
            long start = System.nanoTime();
            KnapsackMemoization.knapsack(weights, values, capacity);
            long end = System.nanoTime();
            System.out.print((end - start) / 1000 + "μs\t\t");
            
            // Tabulation
            start = System.nanoTime();
            KnapsackTabulation.knapsack(weights, values, capacity);
            end = System.nanoTime();
            System.out.print((end - start) / 1000 + "μs\t\t");
            
            // Optimized
            start = System.nanoTime();
            KnapsackOptimized.knapsackSingleArray(weights, values, capacity);
            end = System.nanoTime();
            System.out.print((end - start) / 1000 + "μs");
            
            System.out.println();
        }
    }
    
    public static void main(String[] args) {
        comparePerformance();
    }
}

Müsahibə Sualları

1. Əsas 0/1 Knapsack

Sual: Maksimum dəyəri əldə etmək üçün hansı əşyaları seçməlisiniz? Cavab: DP ilə O(n*W) həll

2. Unbounded Knapsack

Sual: Hər əşyadan istənilən sayda götürə bilərsinizsə? Cavab: Coin Change-ə oxşar, lakin maksimizasiya problemi

3. Subset Sum Problem

Sual: Verilmiş cəmə bərabər alt-çoxluq tapın. LeetCode: Problem 416 - Partition Equal Subset Sum

4. Target Sum

Sual: +/- əlavə edərək target sum əldə edin. LeetCode: Problem 494 - Target Sum

5. Fractional Knapsack

Sual: Hissə-hissə götürə bilərsinizsə? Cavab: Greedy algorithm (value/weight ratio-ya görə sırala)

LeetCode Problemləri

1. 416. Partition Equal Subset Sum - https://leetcode.com/problems/partition-equal-subset-sum/ (0/1 Knapsack variantı)

2. 494. Target Sum - https://leetcode.com/problems/target-sum/ (Subset sum problemi)

3. 474. Ones and Zeroes - https://leetcode.com/problems/ones-and-zeroes/ (2D Knapsack)

4. 1049. Last Stone Weight II - https://leetcode.com/problems/last-stone-weight-ii/ (Partition problemi)

5. 518. Coin Change 2 - https://leetcode.com/problems/coin-change-2/ (Unbounded Knapsack)

Real-World Tətbiqləri

1. Resource Allocation: Məhdud büdcə ilə layihə seçimi
2. Portfolio Optimization: İnvestisiya seçimi
3. Cargo Loading: Yük maşınına optimal yükləmə
4. Budget Management: Xərclərin optimallaşdırılması
5. Memory Management: Cache-də hansı məlumatların saxlanması
6. Task Scheduling: CPU və ya GPU task seçimi

Optimizasiya Məsləhətləri

1. Space optimization: O(W) space mümkündür
2. Backward traversal: Single array üçün geriyə doğru traverse
3. Early termination: Maksimum dəyər əldə edilibsə
4. Value/Weight sorting: Bəzi hallarda performansı yaxşılaşdırır
5. Branch and Bound: Daha böyük instance-lər üçün

Fərqlər

0/1 vs Unbounded Knapsack

• 0/1: Hər əşyadan max 1 dəfə
• Unbounded: Hər əşyadan istənilən sayda

0/1 vs Fractional Knapsack

• 0/1: Tam götürmək və ya heç götürməmək (DP)
• Fractional: Hissə-hissə götürə bilərsiniz (Greedy)

Əlaqəli Problemlər

• Subset Sum
• Partition Equal Subset Sum
• Target Sum
• Coin Change
• Rod Cutting
• Minimum Subset Sum Difference
• Count of Subset Sum