Unit 1: Algorithm implementation and analysis

Sort items by profit/weight ratio and take whole items while they fit. It is fast — O(n log n) — but not always optimal for 0/1 knapsack.

cint knapsack(int W, int wt[], int val[], int n) {
    int K[n + 1][W + 1];
    for (int i = 0; i <= n; i++)
        for (int w = 0; w <= W; w++) {
            if (i == 0 || w == 0) K[i][w] = 0;
            else if (wt[i - 1] <= w)
                K[i][w] = (val[i - 1] + K[i - 1][w - wt[i - 1]] > K[i - 1][w])
                          ? val[i - 1] + K[i - 1][w - wt[i - 1]] : K[i - 1][w];
            else K[i][w] = K[i - 1][w];
        }
    return K[n][W];
}

Time and space: O(nW).

Find the order of multiplying matrices A₁A₂…Aₙ (dimensions p₀ × p₁, p₁ × p₂ …) that needs the fewest scalar multiplications. m[i][j] = min over k of (m[i][k] + m[k + 1][j] + pᵢ₋₁ × pₖ × pⱼ), with m[i][i] = 0.

Complexity: O(n³) time, O(n²) space.