Plecak bez ograniczeń i Coin Change II

W problemie Unbounded Knapsack każdy przedmiot można wybrać dowolną liczbę razy (w przeciwieństwie do problemu plecakowego 0/1, w którym każdy przedmiot jest używany najwyżej raz). Definicja stanu pozostaje taka sama — dp[c] = maksymalna wartość osiągalna przy pojemności c — zmienia się jednak kierunek iterowania. Ponieważ przedmioty można ponownie wykorzystywać, podczas aktualizowania dp[c] chcemy dopuścić ponowne użycie bieżącego przedmiotu, dlatego iterujemy pojemność od lewej do prawej (w przód).

Przypomnijmy, że w problemie plecakowym 0/1 iterowaliśmy od prawej do lewej, aby zapobiec ponownemu użyciu przedmiotów. W problemie plecakowym nieograniczonym robimy odwrotnie: iterujemy od lewej do prawej. Podczas obliczania dp[c] wartość dp[c-w] została już zaktualizowana w bieżącym przebiegu — oznacza to, że przedmiot i mógł już zostać uwzględniony. Tego właśnie potrzebujemy: przedmiot i można dodać ponownie do rozwiązania, które już go zawiera.

Problem Coin Change II polega na tym, aby dla danych nominałów monet i kwoty policzyć liczbę różnych sposobów uzyskania tej kwoty (każdej monety można używać bez ograniczeń). Jest to wariant problemu plecakowego nieograniczonego, w którym zamiast maksymalizować wartość, zliczamy kombinacje. Zdefiniujmy dp[c] jako liczbę sposobów uzyskania kwoty c. Przypadek bazowy: dp[0] = 1 (istnieje jeden sposób uzyskania 0: nic nie wybrać).

Dla każdej monety iterujemy po kwotach od lewej do prawej i dodajemy: dp[c] += dp[c - coin]. Przypadek bazowy dp[0] = 1 inicjuje zliczanie. Zauważmy, że pętla zewnętrzna przebiega po monetach, a wewnętrzna po kwotach — dzięki temu naturalnie otrzymujemy liczbę kombinacji (a nie permutacji), ponieważ każdy nominał jest uwzględniany dokładnie raz w osobnym przebiegu pętli zewnętrznej.

Kolejność pętli ma kluczowe znaczenie. Jeśli umieścimy amount w pętli zewnętrznej, a coin w pętli wewnętrznej, będziemy zliczać permutacje (kolejność ma znaczenie). Dla amount=5 i monet [1,2] ciągi 1+2+2 i 2+1+2 zostaną policzone osobno. Jeśli umieścimy coin w pętli zewnętrznej, będziemy zliczać kombinacje (kolejność nie ma znaczenia): 1+2+2 i 2+1+2 są tym samym sposobem. Problem Coin Change II wymaga zliczania kombinacji, dlatego coin znajduje się w pętli zewnętrznej.

Inny klasyczny problem plecakowy nieograniczony: mając pręt o długości n i ceny dla każdej długości pręta od 1 do n, należy znaleźć maksymalny przychód przez optymalne pocięcie pręta. Każdy kawałek o długości l można sprzedać za price[l], a kawałki mogą być używane wielokrotnie (pręt można podzielić na wiele kawałków o tej samej długości). Problem ten bezpośrednio odpowiada problemowi plecakowemu nieograniczonemu, w którym W = n, a przedmiotami są różne długości cięcia.

Coin Change I (inny problem) polega na znalezieniu minimalnej liczby monet potrzebnych do uzyskania docelowej kwoty. W tym przypadku dp[c] = minimalna liczba monet potrzebnych do uzyskania kwoty c. Zależność rekurencyjna: dp[c] = min(dp[c], dp[c - coin] + 1). Wszystkie wpisy należy zainicjalizować wartością inf, z wyjątkiem dp[0] = 0. Jest to również problem nieograniczony (monet można używać wielokrotnie), dlatego iterujemy od lewej do prawej. Zwracamy dp[amount], jeśli wartość jest skończona, w przeciwnym razie -1.

Trzy warianty problemu plecakowego nieograniczonego używają różnych operacji na dp[c-coin]: Maksymalizacja wartości: dp[c] = max(dp[c], dp[c-w] + v); inicjalizacja wartością 0. Minimalizacja kosztu: dp[c] = min(dp[c], dp[c-coin] + 1); inicjalizacja wartością inf, dp[0]=0. Zliczanie sposobów: dp[c] += dp[c-coin]; inicjalizacja wartością 0, dp[0]=1. Rozpoznanie właściwego wariantu to połowa sukcesu w zadaniach rekrutacyjnych.

Wszystkie warianty problemu plecakowego nieograniczonego działają w czasie O(n × W) i zajmują O(W) pamięci, gdzie n oznacza liczbę typów przedmiotów, a W — docelową kwotę. W problemach monetowych n oznacza liczbę nominałów. Podczas rozmowy rekrutacyjnej należy określić wariant (maksimum/minimum/zliczanie), zapisać DP 1D oraz jasno wskazać, czy pętla zewnętrzna przebiega po monetach, czy po kwocie — osoby oceniające wiedzą, że to rozróżnienie sprawdza dogłębne rozumienie DP.

Skorzystaj z poniższych wskazówek, aby rozpoznać właściwy wariant: nieograniczone ponowne użycie → problem nieograniczony (iterowanie w przód); każdy przedmiot dokładnie raz → problem 0/1 (iterowanie wstecz); sformułowania „dowolną liczbę razy”, „nieograniczony zapas” lub „dozwolone ponowne użycie” → problem nieograniczony. Przykłady: coin change, rod cutting i integer break — wszystkie są problemami nieograniczonymi. Subset sum, partition i 0/1 knapsack — to problemy 0/1. Pomyłka na tym etapie prowadzi do błędnych odpowiedzi, które trudno zdebugować.

Integer Break (LeetCode 343): podzielić liczbę n na co najmniej 2 dodatnie liczby całkowite tak, aby zmaksymalizować ich iloczyn. Jest to problem plecakowy nieograniczony, w którym „przedmiotami” są liczby całkowite od 2 do n-1. Zdefiniujmy dp[i] jako maksymalny iloczyn liczb sumujących się do i. Dla każdego przedmiotu j od 2 do i dp[i] = max(dp[i], max(j, dp[j]) * max(i-j, dp[i-j])). Pokazuje to, jak wzorzec problemu nieograniczonego uogólnia się poza kontekstem monet.

Proszę sprawdzić swoją wiedzę na temat zagadnień z kursu Data Structures & Algorithms — Coding Interview Prep omówionych w tej lekcji.

W tej lekcji poznali Państwo: że w problemie plecakowym nieograniczonym iteruje się pojemność od lewej do prawej, aby umożliwić ponowne użycie przedmiotu, że Coin Change II zlicza kombinacje, umieszczając coin w pętli zewnętrznej oraz że trzy warianty — maksymalizacja, minimalizacja i zliczanie — różnią się wyłącznie operacją DP i inicjalizacją. Następnie wykorzystamy problem plecakowy 0/1 do rozwiązania Partition Equal Subset Sum.