一、什么是动态规划

  动态规划（Dynamic Porogramming）是算法的核心是：将大问题划分为小问题进行解决，从而一步步获取最优解的处理算法。动态规划与分治算法类似，不同的是，适用于动态规划求解的问题，经分解得到子问题往往不是互相独立的，即下一个子阶段的求解是建立在上一个子阶段的基础上，进行进一步的求解。

二、背包问题

  背包问题主要是指一个给定容量的背包、若干具有一定价值和重量的物品，如何选取物品放入背包是物品的价值最大。其中，又分为 01 背包和完全背包问题。其中，01 背包 指的是每个物品最多放一个，完全背包 指的是每种物品都有无限件可用。完全背包可以转换为 01 背包。

  背包问题解决的主要思想：利用动态规划来解决。每次遍历到的第 i 个物品，根据 w[i] 和 v[i] 来确定是否需要将物品放入背包中。即对于给定的 n 个物品，设 v[i]、w[i] 分别为第 i 个物品的价值和重量，C 为背包的容量。再另 v[i][j] 表示在前 i 个物品中能够装入容量为 j 的背包中的最大价值。则我们有下面的结果：

// 表示填入表第一行和第一列是0
v[i][0] = v[0][j] = 0; 

// 当准备加入新增的商品大于当前背包的容量时，就直接使用上一个单元格的装入策略   
if(w[i] > j)
{
    v[i][j] = v[i-1][j];
}

// 当准备加入的新增的商品容量小于等于当前背包的容量
// 装入的方式：
// v[i-1][j]：就是上一个单元格的装入的最大值
// v[i]：表示当前商品的价值
// v[i-1][j-w[i]]：装入i-1个商品到剩余空间j-w[i]
if(j >= w[i])
{
    v[i][j] = max(v[i-1][j],v[i]+v[i-1][j-w[i]]);
}

#include <stdio.h>
#include <string.h>
#include <math.h>

int main(void)
{
    int i = 0,j = 0;
    int weight[] = {1,4,3};                         // 物品的重量
    int value[] = {1500,3000,2000};                 // 物品的价值
    int capacity = 4;                               // 背包的容量
    int count = sizeof(value)/sizeof(value[0]);     // 物品的个数

    // 为了记录放入商品的情况，我们定义一个二维数组
    int path[count+1][capacity+1];
    memset(path,0,sizeof(path));

    // v[i][j]表示前i个物品中能够装入容量为j的背包中的最大价值
    int v[count+1][capacity+1];   
    memset(v,0,sizeof(v));
  
    for(i = 1; i < count+1; i++)                    // 不处理第一行
    {
        for(j = 1; j < capacity+1; j++)             // 不处理第一列
        {
            // 当准备加入新增的商品大于当前背包的容量时，就直接使用上一个单元格的装入策略 
            if(weight[i-1] > j)
            {
                v[i][j] = v[i-1][j];
            }
            // 当准备加入的新增的商品容量小于等于当前背包的容量
            // 装入的方式：
            // v[i-1][j]：就是上一个单元格的装入的最大值
            // value[i]：表示当前商品的价值
            // v[i-1][j-w[i]]：装入i-1个商品到剩余空间j-w[i]
            else
            {
                // v[i][j] = fmax(v[i-1][j],value[i-1]+v[i-1][j-weight[i-1]]);
                // 为了记录商品存放背包的情况，我们不能直接使用上面的公式，需要使用if-else来处理
                if(v[i-1][j] < value[i-1] + v[i-1][j-weight[i-1]])
                {
                    v[i][j] = value[i-1] + v[i-1][j-weight[i-1]];
                    // 把当前的情况记录到path
                    path[i][j] = 1;
                }
                else
                {
                    v[i][j] = v[i-1][j];
                }
            }
        }
    }

    // 输出最终我们放入的是哪些商品
    i = count;                                      // 行的最大下标
    j = capacity;                                   // 列的最大下标
    while(i > 0 && j > 0)
    {
        if(path[i][j] == 1)
        {
            printf("第%d个商品放入到背包！\n",i);
            j -= weight[i-1];
        }
        i--;
    }

    return 0;
}