Dynamic programming is a technique that decomposes complex problems in to smaller subproblems, avoiding redundant computations and storing data efficiently to solve multi-stage mathematical problems, thereby improving algorithmic efficiency.

In algorithm design, dynamic programming includes methods such as recursion, linear DP, memoization, knapsack problems, attribute DP, interval DP, digit DP, and state compression DP.

Knapsack Problem in Dynamic Programming

The knapsack problem is a classic application of dynamic programming, focusing on optimizing resource allocation under constraints.

Identifying the Knapsack Problem

Knapsack problems typically involve a total capacity limit, a set of items with values and weights, and the goal is to maximize total value without exceeding capacity. For example, given a knapsack capacity and items with specified weights and values, determine the maximum acheivable value.

Constructing the Knapsack Solution

After identifying a knapsack problem, we can apply a standard template. Start with a simple example to understand the construction process, using tables to visualize the solution.

Example Scenario

Consider a knapsack with capacity 8 and four items, each usable only once:

• Item 1: weight 2, value 3
• Item 2: weight 3, value 4
• Item 3: weight 4, value 5
• Item 4: weight 5, value 6

Building the Solution Table

Define a table where rows represent items (including a dummy row for no items) and columns represent knapsack capacities from 0 to 8. Initialize the first row and column to 0, as no items or zero capacity yield zero value.

For item 1 at capacity 2, it can be included, so value is 3.

At capacity 3 with item 2, two cases arise:

1. Exclude item 2: value remains 3 (from previous row).
2. Include item 2: value is 4 plus the best value for remaining capacity (0), totaling 4.

Compare and select the maximum (4).

Continue this process to fill the table, always choosing the maximum value between excluding or including an item based on remaining capacity.

Implementing the Data Structure

Use a 2D array dp with dimansions (N+1) x (W+1), where N is the number of items and W is the cpaacity. Index 0 is reserved for base cases with zero value.

Initialize with item values and weights arrays, then iterate to compute optimal values.

Algorithm Logic

Two main cases based on item weight relative to current capacity:

1. If item weeight exceeds capacity, cannot include: dp[i][j] = dp[i-1][j].
2. If item weight is within capacity, consider:
   • Excluding: dp[i-1][j]
   • Including: value[i] + dp[i-1][j - weight[i]] Set dp[i][j] to the maximum of these two.

Code implementation:

int[][] dp = new int[numItems + 1][capacity + 1];
for (int i = 1; i <= numItems; i++) {
    for (int j = 0; j <= capacity; j++) {
        if (itemWeights[i] > j) {
            dp[i][j] = dp[i-1][j];
        } else {
            dp[i][j] = Math.max(dp[i-1][j], itemValues[i] + dp[i-1][j - itemWeights[i]]);
        }
    }
}

Practical Exercise

Apply this to Luogu problem P1048, where time is the capacity and herbs are items with time costs and values.

Problem: Given total time T and M herbs with time and value, maximize total value.

Input example:

70 3
71 100
69 1
1 2

Output: 3

Solution code:

import java.util.Scanner;

public class HerbCollection {
    public static void main(String[] args) {
        Scanner input = new Scanner(System.in);
        int totalTime = input.nextInt();
        int herbCount = input.nextInt();
        int[] times = new int[herbCount + 1];
        int[] values = new int[herbCount + 1];
        for (int i = 1; i <= herbCount; i++) {
            times[i] = input.nextInt();
            values[i] = input.nextInt();
        }
        int[][] result = new int[herbCount + 1][totalTime + 1];
        for (int i = 1; i <= herbCount; i++) {
            for (int j = 0; j <= totalTime; j++) {
                if (times[i] > j) {
                    result[i][j] = result[i-1][j];
                } else {
                    result[i][j] = Math.max(values[i] + result[i-1][j - times[i]], result[i-1][j]);
                }
            }
        }
        System.out.println(result[herbCount][totalTime]);
    }
}