DP Visualizers

Min Houses — Knapsack

Houses (candy counts)

G (capacity)

🎃 Copilul triseaza (unbounded)

Delay 400ms

Algorithm (C++)

                    for (int s=0; s<=G; s++) dp[s]=INF;
                    dp[0]=0;
                     
                    for (int i=0; i<n; i++) {          // fiecare casa
                      for (int s=G; s>=g[i]; s--) {   // descrescator! (0/1)
                        if (dp[s-g[i]]+1 < dp[s]) {
                          dp[s] = dp[s-g[i]]+1;
                          from[s] = i;  // retine casa
                        }
                      }
                    }
                

dp[s] — minim case pentru capacitate s

from[s] — ultima casa care a actualizat dp[s]