demo_knapsack_problem_1.cpp

#include <iostream>
#include <algorithm>
using namespace std;

/***
 * 
 * 最优性原理：多阶段决策过程的最优决策序列具有这样的性质：不论初始状态和初始决策如何，对于前面决策所造成的某一状态而言，其后各阶段的决策序列必须构成最优策略
 * 
 * 有n个物品，它们有各自的体积和价值。现有给定容量的背包，如何让背包里装入的物品具有最大的价值总和？
 * 递归关系。面对当前商品有两种可能性
 *  1. 包的容量比该商品体积小，装不下，此时的价值与前 i - 1 个的价值是一样的，即 V(i, j) = V(i - 1, j)
 *  2. 还有足够的容量可以装该商品，但装里也不一定达到当前最有价值，所以在装与不装之间选择最优的一个，即V(i, j) = max{V(i - 1, j), V(i - 1, j - w(i) + v(i))}
 *     1. V(v - 1, j) 表示不装， V(i - 1, j - w(i)) + v(i) 表示装了第i个商品，背包容量减少w(i), 但价值增加了v(i)
 *     2. 如果装进入第i件商品，那么装进去之前是什么状态，肯定是V(i - 1, j - w(i))
 *  3. 公式
 *      1. j < w(i). V(i, j) = V(i - i, j)
 *      2. j >= w(i). V(i, j) = max{V(i - 1, j), V(i - 1, j - w(i)) + v(i)}
 */
int main () 
{ 
    int w[5] = {0, 2, 3, 4, 5};     // 商品的体积2，3，4，5
    int v[5] = {0, 3, 4, 5, 6};     // 商品的价值3,4,5,6

    int bagV = 8;                   // 背包大小（容量）
    int dp[5][9] = {{0}};           // 动态规划表

    for (int i = 1; i <= 4; i++) {
        for (int j = 1; j <= bagV; j++) {
            if (j < w[i]) {
                dp[i][j] = dp[i - 1][j];
            } else {
                dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - w[i]] + v[i]);
            }
        }
    }

    // 动态规划表的输出
    for (int i = 0; i < 5; i++) {
        for (int j = 0; j < 9; j++) {
            cout << dp[i][j] << ' ';
        }
        cout << endl;
    }
    return 0;
}