一、什么是动态规划
动态规划（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]]);
}
| 物品 | 重量 | 价值 |
|---|---|---|
| 吉他（G） | 1 | 1500 |
| 音响（S） | 4 | 3000 |
| 电脑（L） | 3 | 2000 |
| 物品 | 0 磅 | 1 磅 | 2 磅 | 3 磅 | 4 磅 |
|---|---|---|---|---|---|
| 0 | 0 | 0 | 0 | 0 | |
| 吉他（G） | 0 | 1500（G） | 1500（G） | 1500（G） | 1500（G） |
| 音响（S） | 0 | 1500（G） | 1500（G） | 1500（G） | 3000（G） |
| 电脑（L） | 0 | 1500（G） | 1500（G） | 2000（G） | 2000（L）+ 1500（G） |
#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;
}