0 1 Knapsack Problem in DSA Typescript - Interactive Practice

Practice - 5 Tasks

1fill in blank

easy

Complete the code to initialize the DP array for the knapsack problem.

DSA Typescript

const dp: number[][] = Array(n + 1).fill(null).map(() => Array([1] + 1).fill(0));

Drag options to blanks, or click blank then click option'

AW

Bn

Cweights.length

Dvalues.length

Attempts:

3 left

💡 Hint

Common Mistakes

Using the number of items instead of the weight capacity for dp array size.

Confusing the length of values or weights arrays with the weight capacity.

The DP array has dimensions (n+1) x (W+1), where W is the maximum weight capacity.

2fill in blank

medium

Complete the code to check if the current item's weight fits in the current capacity.

DSA Typescript

if (weights[i - 1] [1] w) {

Drag options to blanks, or click blank then click option'

A<

B>

C==

D<=

Attempts:

3 left

💡 Hint

Common Mistakes

Using '>' which checks if the item is too heavy instead of fits.

Using '==' which excludes items lighter than capacity.

We check if the item's weight is less than or equal to the current capacity to decide if we can include it.

3fill in blank

hard

Fix the error in the code to correctly update the DP value when including the current item.

DSA Typescript

dp[i][w] = Math.max(dp[i - 1][w], dp[i - 1][w - [1]] + values[i - 1]);

Drag options to blanks, or click blank then click option'

Avalues[i - 1]

Bweights[i]

Cweights[i - 1]

Dvalues[i]

Attempts:

3 left

💡 Hint

Common Mistakes

Using weights[i] causes index out of range error.

Using values instead of weights for capacity subtraction.

We subtract the weight of the current item (weights[i - 1]) from the capacity to find the remaining capacity.

4fill in blank

hard

Fill both blanks to complete the loop headers for the DP table construction.

DSA Typescript

for (let i = 1; i [1] n + 1; i++) {
  for (let w = 0; w [2] W + 1; w++) {

Drag options to blanks, or click blank then click option'

A<

B<=

C>

D>=

Attempts:

3 left

💡 Hint

Common Mistakes

Using '<=' causes index out of range errors.

Using '>' or '>=' causes infinite loops or no iteration.

Loops run from 1 to n (exclusive of n+1) and 0 to W (exclusive of W+1) using '<' operator.

5fill in blank

hard

Fill all three blanks to complete the function signature and return statement for the knapsack solution.

DSA Typescript

function knapsack([1]: number[], [2]: number[], [3]: number): number {
  // function body
  return dp[n][W];
}

Drag options to blanks, or click blank then click option'

Aweights

BW

Cn

Dvalues

Attempts:

3 left

💡 Hint

Common Mistakes

Mixing up weights and values in the parameter list.

Incorrect order of parameters causing confusion.

The function takes values array, weights array, and weight capacity W as parameters.