是什么

动态规划(dynamic programming)是求解决策过程最优化的数学方法，把多阶段过程转换为一系列单阶段问题，利用各阶段之间的关系，逐个求解，创立了解决这类过程优化问题的新方法。

基本思想

将待求解的问题分解成若干个子问题，先求解子问题，然后从这些子问题的解得到原问题的解。

求解步骤

找出最优解的性质，刻画出结构特征
递归的定义最优解的值
自底向上的方式计算最优值（例如0/1背包问题将价值从低到高排序，再依次像背包中放入，调整）
根据最优值构造最优解（求出哪些物品放在了背包中，标记为1，否则标记为0）

0-1背包问题

问题描述

现在有5个物品，第i个物品的价值为vi,重量为wi，背包的容量为W，其中的参数都为非负数，W=17。求解如何放物品使得背包的总价值最大。假设我们将物品的价值从低到高排好序如下表：

物品的价值和重量
物品编号	1	2	3	4	5
价值v	4	5	10	11	13
重量w	3	4	7	8	9

问题分析

尝试将1号物品放入背包

1号物品重量为3，我们先将背包分成从0到17，共18份，当背包容量是0时，物品1无法放入背包，所以最大价值为0，依次类推，当背包的容量为3时，刚好可以将1号物品放入背包，则此时背包中最大价值为4（即为物品1的价值，位置为下表格标红处），背包容量依次增大到17，背包中还是盛放1号物品，所以，将1号物品放入背包的最大价值为4。

动态规划法示例
I\W	0	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16	17
1	0	0	0	4	4	4	4	4	4	4	4	4	4	4	4	4	4	4

尝试将2号物品放入背包

2号物品的重量是4，价值为5，当背包的容量为4时，可以考虑放入物品2或者物品1，因为物品2的价值>物品1的价值，所以将物品2放入背包，此时背包的最大价值为5（如下表格中第三行第一个标红的位置），背包容量逐渐增大，当背包容量为7时，可以将物品1和物品2都放入背包，此时背包内最大价值为9（物品1价值+物品2价值），背包容量递增至17，都是放入物品1和物品2，所以结果是最大价值为9。

动态规划法示例
I\W	0	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16	17
1	0	0	0	4	4	4	4	4	4	4	4	4	4	4	4	4	4	4
2	0	0	0	4	5	5	5	9	9	9	9	9	9	9	9	9	9	9

尝试将3号物品放入背包

3号物品的重量为7，价值为10，背包容量为0~6时，最大价值和上一行（表格第三行）相同，当背包容量为7时物品3的价值大于上一行时的价值，需要调整，直至背包容量为10时，背包中可放入物品1和物品3，且两者价值之和大于当前最大价值，需要调整为4+10=14，当背包容量增至14时可以放入物品1、物品2和物品3，且三者价值之和大于当前最大价值，所以调整为4+5+10=19，背包容量达到17时仍然放这三个物品，所以结果为当前最大价值是19.

动态规划法示例
I\W	3	4	5	6	7	8	9	10	11	12	13	14	15	16	17
1	4	4	4	4	4	4	4	4	4	4	4	4	4	4	4
2	4	5	5	5	9	9	9	9	9	9	9	9	9	9	9
3	4	5	5	5	10	10	10	14	14	14	14	19	19	19	19

尝试将4号物品放入背包

4号物品的重量为8，价值为11，在背包容量为0~7时，背包内的最大价值与上一行相同，容量增加到8时可尝试将物品4放入，物品4的价值大于当前最大价值，则条换为11，当背包容量增至11时刻尝试放入物品1和物品4，且价值之和大于当前最大价值，则调整为15，背包容量为12时刻尝试放入物品2和物品4，且价值之和大于当前最大价值，则调整为16，背包容量增至15时可尝试放入物品3和物品4，且价值之和大于当前最大价值，则调整为21，直至背包容量增加至17时一直存放物品3和物品4为最大价值，则结果为当前最大价值是21.

动态规划法示例
I\W	3	4	5	6	7	8	9	10	11	12	13	14	15	16	17
1	4	4	4	4	4	4	4	4	4	4	4	4	4	4	4
2	4	5	5	5	9	9	9	9	9	9	9	9	9	9	9
3	4	5	5	5	10	10	10	14	14	14	14	19	19	19	19
4	4	5	5	5	10	11	11	14	15	16	16	19	21	21	21

尝试将5号物品放入背包

物品5的重量为9，价值为13，则背包容量在0~8时最大价值和上一行相同，背包容量为9时刻考虑放入物品5，且物品5的价值比当前价值要大，所以进行调整，当前最大价值为13，背包容量增至12时刻考虑放入物品1和物品5，且价值之和大于当前最大价值，调整，当前最大价值为17，背包容量为13时，考虑放入物品2和物品5，且价值之和大于当前最大价值，调整，当前最大价值为18，背包容量增至16时考虑放入物品3和物品5，且价值之和大于当前最大价值，调整，当前最大价值为23，背包容量增至17时，考虑放入物品4和物品5，价值之和大于当前最大价值，调整，当前最大价值为24，则结果为当前最大价值为24.

动态规划法示例
I\W	3	4	5	6	7	8	9	10	11	12	13	14	15	16	17
1	4	4	4	4	4	4	4	4	4	4	4	4	4	4	4
2	4	5	5	5	9	9	9	9	9	9	9	9	9	9	9
3	4	5	5	5	10	10	10	14	14	14	14	19	19	19	19
4	4	5	5	5	10	11	11	14	15	16	16	19	21	21	21
5	4	5	5	5	10	11	13	14	15	17	18	19	21	23	24

代码示例

递归定义最优解的值

计算背包最优解的值

int **KnasackDP(int n,int* Weights,float* Values){
int i,w;/*物品编号和背包剩余容量*/

/*为二维数组申请空间*/
int** c=(int**)malloc(sizeof(int*)*(n+1));

/*声明一个一维数组存放物品*/
for(i=0;i<=n;i++)
c[i]=(int*)malloc(sizeof(int)*(W+1));

/*初始化二维数组*/
for(w=0;w<=W;w++)
/*0个物品放入背包中，价值为0*/
c[0][w]=0;

for(i=1;i<=n;i++){
/*i个物品放到容量为0的背包中，价值为0*/
c[i][0]=0;

for(w=1;w<=W;w++){
if(Weights[i-1]<=w){/*背包剩余容量大于物品重量*/
/*将当前物品放入背包的最大价值>不放的最大价值*/
if(Weights[i-1]+c[i-1][w-Weights[i-1]]>c[i-1][w])
{
/*重量为w的背包中放入该物品*/
c[i][w]=Values[i-1]+c[i-1][w-Weights[i-1]];
}
else{
/*重量为w的背包中不放入该物品*/
c[i][w]=c[i-1][w];
}
    }
    else
/*若物品重量不小于背包容量w，则不放入该物品
c[i][w]=c[i-1][w];
}
}
/*返回最优值*/
return c;
}

构造最优解

void OutputKnapsackDP(int n,int W,int *Weights,float *Values,int **c){
int x[n];
int i;
for(i=n;i>1;i--){

if(c[i][W]==c[i-1][W])
/*物品i没有放入背包，存0*/
x[i-1]=0;
else{
/*物品i放入背包，存1*/
x[i-1]=1;W=W-Weights[i-1];
}
}

if(c[1][W]==0)
/*第一个物品不放入背包*/
x[0]=0;
else
/*第一个物品放入背包*/
x[0]=1;

for(i=0;i<n;i++)
if(x[i]==1)
/*打印出放入背包的物品重量和对应价值*/
printf("Weigh:%d,Value:%f\n",Weights[i],Values[i]);
}

总结

1.每一步的解为当前的最优解 2.存放物品时不存在不完整的情况，只能是将整个物品放入背包或不放入背包两种情况 3.求出最优解够需要构造最优解，判断出都是哪些物品放进了背包

秒客网

动态规划法解决0/1背包问题详解

是什么