Exercism - Knapsack | Stevinator

Preparation

Before we click on our next exercise, let’s see what concepts of DART we need to consider

So we need to use the following concepts.

Typedef

Typedef creates a type alias, giving a name to a type. It’s perfect for making complex types like records more readable and reusable.

// Define a type alias for a record
typedef Item = ({int weight, int value});

void main() {
  // Use the typedef
  Item item1 = (weight: 5, value: 10);
  Item item2 = (weight: 4, value: 40);
  
  // Access fields
  print(item1.weight); // 5
  print(item1.value); // 10
  
  // Use in lists
  List<Item> items = [
    (weight: 5, value: 10),
    (weight: 4, value: 40),
  ];
}

Records (Named Records)

Records allow you to group multiple values together with named fields. They’re perfect for representing items with weight and value.

void main() {
  // Named record syntax: (field1: value1, field2: value2)
  var item = (weight: 5, value: 10);
  print(item); // (weight: 5, value: 10)
  
  // Access named fields
  print(item.weight); // 5
  print(item.value); // 10
  
  // Use in lists
  List<({int weight, int value})> items = [
    (weight: 5, value: 10),
    (weight: 4, value: 40),
  ];
  
  // Iterate and access
  for (var item in items) {
    print('Weight: ${item.weight}, Value: ${item.value}');
  }
}

Classes and Constructors

Classes define blueprints for objects. Constructors initialize instances with specific values.

class Knapsack {
  final int maxWeight;
  
  // Constructor with named parameter
  Knapsack({required this.maxWeight});
}

void main() {
  Knapsack knapsack = Knapsack(maxWeight: 10);
  print(knapsack.maxWeight); // 10
}

2D Lists (Dynamic Programming Tables)

2D lists are lists of lists, creating a matrix structure. They’re perfect for dynamic programming tables where dp[i][w] represents a subproblem solution.

void main() {
  int n = 4; // number of items
  int maxWeight = 10;
  
  // Create DP table: dp[i][w] = max value with first i items and weight w
  List<List<int>> dp = List.generate(n + 1, (_) => List.filled(maxWeight + 1, 0));
  
  // Access elements
  dp[0][0] = 0; // Base case
  dp[1][5] = 10; // Value with first item at weight 5
  
  // Example structure:
  // dp[0] = [0, 0, 0, ..., 0] (no items)
  // dp[1] = [0, 0, 0, ..., 10] (first item)
  // dp[2] = [0, 0, 0, ..., 40] (first two items)
}

List `generate()` and `filled()` for DP Tables

The combination of List.generate() and List.filled() is perfect for creating dynamic programming tables initialized with zeros.

void main() {
  int n = 4;
  int maxWeight = 10;
  
  // Create DP table: (n+1) rows × (maxWeight+1) columns
  List<List<int>> dp = List.generate(
    n + 1,                    // Number of rows
    (_) => List.filled(maxWeight + 1, 0)  // Each row filled with zeros
  );
  
  // dp[i][w] represents max value with first i items and weight limit w
  // dp[0][w] = 0 (no items, value is 0)
  // dp[i][0] = 0 (no weight capacity, value is 0)
}

Nested For Loops

Nested for loops allow you to iterate through multiple dimensions. They’re essential for filling dynamic programming tables.

void main() {
  int n = 4;
  int maxWeight = 10;
  List<List<int>> dp = List.generate(n + 1, (_) => List.filled(maxWeight + 1, 0));
  
  // Outer loop: iterate through items
  for (int i = 1; i <= n; i++) {
    // Inner loop: iterate through weights
    for (int w = 0; w <= maxWeight; w++) {
      // Calculate dp[i][w]
      dp[i][w] = calculateValue(i, w);
    }
  }
}

Dynamic Programming

Dynamic programming solves complex problems by breaking them into smaller subproblems and storing results. The knapsack problem uses a 2D table where dp[i][w] represents the maximum value achievable with the first i items and weight limit w.

void main() {
  // DP approach for knapsack:
  // For each item i and weight w:
  //   Option 1: Don't take item i → dp[i-1][w]
  //   Option 2: Take item i → dp[i-1][w-weight] + value
  //   dp[i][w] = max(Option 1, Option 2)
  
  // Base cases:
  // dp[0][w] = 0 (no items, value is 0)
  // dp[i][0] = 0 (no weight, value is 0)
  
  // Fill table bottom-up
  for (int i = 1; i <= n; i++) {
    for (int w = 1; w <= maxWeight; w++) {
      // Calculate optimal value
    }
  }
  
  // Answer: dp[n][maxWeight]
}

Conditional (Ternary) Operator

The ternary operator (? :) provides a concise way to write if-else statements. It’s useful for choosing the maximum of two values.

void main() {
  int option1 = 10;
  int option2 = 20;
  
  // Ternary operator for max
  int max = option1 > option2 ? option1 : option2;
  print(max); // 20
  
  // Use in DP
  int valueWithoutItem = dp[i - 1][w];
  int valueWithItem = dp[i - 1][w - weight] + value;
  dp[i][w] = valueWithoutItem > valueWithItem 
      ? valueWithoutItem 
      : valueWithItem;
}

Comparison Operators

Comparison operators (>, <=) compare values and return boolean results. They’re used to check if items fit and to choose maximum values.

void main() {
  int itemWeight = 5;
  int currentWeight = 8;
  
  // Check if item fits
  if (itemWeight <= currentWeight) {
    print('Item fits');
  }
  
  // Compare values
  int value1 = 10;
  int value2 = 20;
  if (value1 > value2) {
    print('Value1 is larger');
  } else {
    print('Value2 is larger');
  }
}

Arithmetic Operations

Arithmetic operations like addition (+) and subtraction (-) are used to calculate values and remaining weights.

void main() {
  int currentWeight = 8;
  int itemWeight = 5;
  
  // Calculate remaining weight
  int remainingWeight = currentWeight - itemWeight;
  print(remainingWeight); // 3
  
  // Calculate total value
  int baseValue = 10;
  int itemValue = 20;
  int totalValue = baseValue + itemValue;
  print(totalValue); // 30
  
  // Use in DP
  int valueWithItem = dp[i - 1][w - itemWeight] + itemValue;
}

List Indexing

List indexing allows you to access elements by position. In DP tables, dp[i][w] accesses the value at row i and column w.

void main() {
  List<List<int>> dp = [
    [0, 0, 0],
    [0, 10, 10],
    [0, 10, 40],
  ];
  
  // Access by indices
  int value = dp[1][2]; // Row 1, column 2
  print(value); // 10
  
  // Use in DP calculation
  int previousValue = dp[i - 1][w]; // Value without current item
  int valueWithItem = dp[i - 1][w - weight] + value; // Value with item
}

Introduction

Lhakpa is a Sherpa mountain guide and porter. After months of careful planning, the expedition Lhakpa works for is about to leave. She will be paid the value she carried to the base camp.

In front of her are many items, each with a value and weight. Lhakpa would gladly take all of the items, but her knapsack can only hold so much weight.

Instructions

Your task is to determine which items to take so that the total value of her selection is maximized, taking into account the knapsack’s carrying capacity.

Items will be represented as a list of items. Each item will have a weight and value. All values given will be strictly positive. Lhakpa can take only one of each item.

Example

Items:

[
  { "weight": 5, "value": 10 },
  { "weight": 4, "value": 40 },
  { "weight": 6, "value": 30 },
  { "weight": 4, "value": 50 }
]

Knapsack Maximum Weight: 10

For the above, the first item has weight 5 and value 10, the second item has weight 4 and value 40, and so on. In this example, Lhakpa should take the second and fourth item to maximize her value, which, in this case, is 90. She cannot get more than 90 as her knapsack has a weight limit of 10.

How do we solve the knapsack problem?

To solve the knapsack problem using dynamic programming:

Create DP table: dp[i][w] = maximum value with first i items and weight limit w
Base cases:
- dp[0][w] = 0 (no items, value is 0)
- dp[i][0] = 0 (no weight capacity, value is 0)
Fill table: For each item i and weight w:
- Option 1: Don’t take item i → dp[i-1][w]
- Option 2: Take item i (if it fits) → dp[i-1][w-weight] + value
- dp[i][w] = max(Option 1, Option 2)
Return answer: dp[n][maxWeight] contains the maximum value

The key insight is that each subproblem dp[i][w] builds on previous subproblems, allowing us to find the optimal solution by considering all combinations of items and weights.

Solution

typedef Item = ({int weight, int value});

class Knapsack {
  final int maxWeight;

  Knapsack({required this.maxWeight});

  int maxValue(List<Item> items) {
    if (items.isEmpty || maxWeight == 0) {
      return 0;
    }

    // Create a DP table where dp[i][w] represents the maximum value
    // that can be achieved with the first i items and weight limit w
    final n = items.length;
    final dp = List.generate(n + 1, (_) => List.filled(maxWeight + 1, 0));

    // Build the DP table
    for (int i = 1; i <= n; i++) {
      final item = items[i - 1];
      final itemWeight = item.weight;
      final itemValue = item.value;

      for (int w = 0; w <= maxWeight; w++) {
        // Option 1: Don't take the current item
        dp[i][w] = dp[i - 1][w];

        // Option 2: Take the current item (if it fits)
        if (itemWeight <= w) {
          final valueWithItem = dp[i - 1][w - itemWeight] + itemValue;
          dp[i][w] = dp[i][w] > valueWithItem ? dp[i][w] : valueWithItem;
        }
      }
    }

    return dp[n][maxWeight];
  }
}

Let’s break down the solution:

typedef Item = ({int weight, int value}) - Type alias:
- Creates a type alias for a record with named fields
- Makes Item a reusable type
- Represents an item with weight and value
class Knapsack - Main class:
- Encapsulates the knapsack problem solver
- Stores maximum weight capacity
final int maxWeight - Weight limit:
- Maximum weight the knapsack can carry
- Used to bound the DP table columns
Knapsack({required this.maxWeight}) - Constructor:
- Takes maximum weight as required named parameter
- Initializes the weight limit
int maxValue(List<Item> items) - Main method:
- Takes list of items (each with weight and value)
- Returns maximum value achievable
- Uses dynamic programming approach
if (items.isEmpty || maxWeight == 0) return 0 - Edge cases:
- If no items or no weight capacity, value is 0
- Early return for efficiency
final n = items.length - Number of items:
- Stores item count for convenience
- Used for DP table dimensions
final dp = List.generate(n + 1, (_) => List.filled(maxWeight + 1, 0)) - Create DP table:
- Creates 2D list: (n+1) rows × (maxWeight+1) columns
- n+1 rows: 0 to n items (row 0 = no items)
- maxWeight+1 columns: 0 to maxWeight (column 0 = no weight)
- All initialized to 0 (base cases)
for (int i = 1; i <= n; i++) - Outer loop (items):
- Iterates through each item (1 to n)
- Row 0 is base case (already 0), start from row 1
final item = items[i - 1] - Get current item:
- Accesses item at index i-1 (0-indexed list)
- Row i corresponds to first i items
final itemWeight = item.weight and final itemValue = item.value - Extract item properties:
- Gets weight and value from current item
- Used in calculations
for (int w = 0; w <= maxWeight; w++) - Inner loop (weights):
- Iterates through all possible weights (0 to maxWeight)
- Calculates optimal value for each weight limit
dp[i][w] = dp[i - 1][w] - Option 1: Don’t take item:
- Base value: maximum value without current item
- Inherits value from previous row (same weight)
- This is the default (minimum) value
if (itemWeight <= w) - Check if item fits:
- Only consider taking item if it fits in current weight limit
- Prevents negative weight indices
final valueWithItem = dp[i - 1][w - itemWeight] + itemValue - Option 2: Take item:
- Calculates value if we take current item
- Uses value from dp[i-1][w - itemWeight] (remaining weight after taking item)
- Adds current item’s value
- Example: w=10, weight=4 → use dp[i-1][6] + value
dp[i][w] = dp[i][w] > valueWithItem ? dp[i][w] : valueWithItem - Choose maximum:
- Compares Option 1 (don’t take) vs Option 2 (take)
- Updates dp[i][w] with the better option
- Ternary operator for concise max operation
return dp[n][maxWeight] - Return answer:
- Returns value at dp[n][maxWeight]
- Represents maximum value with all n items and full weight capacity
- This is the optimal solution

The solution efficiently solves the knapsack problem using dynamic programming. The 2D table stores solutions to all subproblems, allowing the algorithm to find the optimal combination of items that maximizes value while respecting the weight constraint. The time complexity is O(n × maxWeight) and space complexity is O(n × maxWeight).

A video tutorial for this exercise is coming soon! In the meantime, check out my YouTube channel for more Dart and Flutter tutorials. 😉

Visit My YouTube Channel