Implement Dynamic Programming in a cake shop (with code)

Suppose you own a cake shop and decided to redecide your menu because you want to maximize your profit by selecting the most valuable cakes to include in your menu.
Each cake has a weight ( chota cake, mota cake) and a value (paisaaa).
The goal is to determine the maximum total value you can obtain with a given maximum weight capacity for your menu.

Code explanation
1) Initialize the Table (menu banane ke lie page toh laoge na)

const dp = Array(cakes.length + 1).fill(null).map(() => Array(capacity + 1).fill(0));

This line initializes a 2D array (dp) to store solutions to subproblems. The array has rows for each cake and columns for different weight capacities.

2) Dynamic Programming Iteration:
for (let i = 1; i <= cakes.length; i++) { const currentCake = cakes[i - 1]; for (let w = 0; w <= capacity; w++) {
The outer loop (i) goes through each cake, and the inner loop (w) goes through each possible weight capacity.

3)Decision Making:
if (currentCake.weight > w) { // If the current cake is too heavy for the remaining capacity, skip it
dp[i][w] = dp[i - 1][w]; } else { // Max value between including and excluding the current cake
dp[i][w] = Math.max(dp[i - 1][w], dp[i - 1][w - currentCake.weight] + currentCake.value); }
Here, the code decides whether to include the current cake or not. If the cake is too heavy for the remaining capacity, it skips it. Otherwise, it calculates the maximum value between including the current cake and excluding it.

4) Result Extraction: (bas ab menu print kr do)

return dp[cakes.length][capacity];

The final result is stored in the bottom-right cell of the dp table, representing the maximum profit considering all cakes and the given capacity.

Example Usage:
const cakes = [ { weight: 2, value: 15 }, { weight: 3, value: 20 }, { weight: 1, value: 10 }, ]; const capacity = 5; const maxProfit = maxCakeValue(cakes, capacity); console.log("Maximum profit:", maxProfit);

Real-world Explanation:
The maxCakeValue function helps you decide which cakes to include in your menu to maximize your profit, given the limited space (capacity) available on your menu display. The example usage with the cakes array and capacity variable shows how you can apply this function to find the maximum profit for your specific cakes and menu capacity.

Developer Rounit ❌
Baker Rounit ✅