算法学习之背包问题-动态规划经典应用

问题要求：

有一个背包，它的容量为C(Capacity)，现在有n中不同的物品，编号为0...n-1，其中每一件物品的重量为w(i)，价值为v(i)。问可以向这个背包中盛放哪些物品，使得在不超过背包容量的基础上，物品的总价值最大。

递归解题代码：

class Knapsack01 {
private:
    vector<vector<int>> memo;
    // 用 [0...index] 的物品， 填充溶剂为c的背包的最大价值
    int bestValue(const vector<int>& w, const vector<int>& v, int index, int c) {
        if (index < 0 || c <= 0)
            return 0;

        if (memo[index][c] != -1)
            return memo[index][c];

        int res = bestValue(w, v, index - 1, c);
        if (c >= w[index])
            res = max(res, v[index] + bestValue(w, v, index - 1, c - w[index]));

        memo[index][c] =  res;
        return res;
    }
public:
    int knapsack01(const vector<int>& w, const vector<int>& v, int C) {

        int n = w.size();
        memo = vector<vector<int>>(n, vector<int>(C + 1, -1));
        return bestValue(w, v, n - 1, C);
    }
};

动态规划代码逻辑：

class Knapsack01 {
public:
    int knapsack01(const vector<int>& w, const vector<int>& v, int C) {
        assert(w.size() != v.size());
        int n = w.size();

        if (n == 0)
            return 0;

        vector<vector<int>> memo(n, vector<int>(C + 1, -1));
        for (int j = 0; j <= C; ++j) {
            memo[0][j] = (j >= w[0] ? v[0] : 0);
        }

        for (int i = 1; i < n; ++i) {
            for (int j = 0; j <= C; ++j) {
                memo[i][j] = memo[i - 1][j];
                if (j >= w[i])
                    memo[i][j] = max(memo[i][j], v[i] + memo[i - 1][j - w[i]]);
            }
        }

        return memo[n - 1][C];

    }
};

进一步的优化：

class Knapsack01 {
public:
    int knapsack01(const vector<int> &w, const vector<int> &v, int C) {
        assert(w.size() != v.size());
        int n = w.size();

        if (n == 0)
            return 0;

        vector<vector<int>> memo(2, vector<int>(C + 1, -1));
        for (int j = 0; j <= C; ++j) {
            memo[0][j] = (j >= w[0] ? v[0] : 0);
        }

        for (int i = 1; i < n; ++i) {
            for (int j = 0; j <= C; ++j) {
                memo[i % 2][j] = memo[(i - 1) % 2][j];
                if (j >= w[i])
                    memo[i % 2][j] = max(memo[i % 2][j], v[i] + memo[(i - 1) % 2][j - w[i]]);
            }
        }

        return memo[(n - 1) % 2][C];

    }
};

再次优化

class Knapsack01 {
public:
    int knapsack01(const vector<int> &w, const vector<int> &v, int C) {
        assert(w.size() != v.size());
        int n = w.size();
        if (n == 0)
            return 0;

        vector<int> memo(C + 1, -1);
        for (int j = 0; j <= C; ++j) {
            memo[j] = (j >= w[0] ? v[0] : 0);
        }

        for (int i = 1; i < n; ++i) {
            for (int j = C; j >= w[i]; j--) {
                memo[j] = max(memo[j], v[i] + memo[j - w[i]]);
            }
        }
        return memo[C];
    }
};