数据结构基础从01背包问题理解动态规划

女爷i 2022-08-08 17:42 124阅读 0赞

01背包问题具体例子：假设现有容量10kg的背包，另外有3个物品，分别为a1，a2，a3。物品a1重量为3kg，价值为4；物品a2重量为4kg，价值为5；物品a3重量为5kg，价值为6。将哪些物品放入背包可使得背包中的总价值最大？

这个问题有两种解法，动态规划和贪婪算法。本文仅涉及动态规划。

先不套用动态规划的具体定义，试着想，碰见这种题目，怎么解决?

首先想到的，一般是穷举法，一个一个地试，对于数目小的例子适用，如果容量增大，物品增多，这种方法就无用武之地了。

其次，可以先把价值最大的物体放入，这已经是贪婪算法的雏形了。如果不添加某些特定条件，结果未必可行。

最后，就是动态规划的思路了。先将原始问题一般化，欲求背包能够获得的总价值，即欲求前**i**个物体放入容量为**m**（kg）背包的最大价值 **c\[i\]\[m\]** —— 使用一个数组来存储最大价值，当**m**取**10**，**i**取**3**时，即原始问题了。而前**i**个物体放入容量为**m（kg）**的背包，又可以转化成前**(i-1)**个物体放入背包的问题。下面使用数学表达式描述它们两者之间的具体关系。

表达式中各个符号的具体含义。

w\[i\] : 第i个物体的重量；

p\[i\] : 第i个物体的价值；

c\[i\]\[m\] ： 前i个物体放入容量为m的背包的最大价值；

c\[i-1\]\[m\] ： 前i-1个物体放入容量为m的背包的最大价值；

c\[i-1\]\[m-w\[i\]\] ： 前i-1个物体放入容量为m-w\[i\]的背包的最大价值；

由此可得：

c\[i\]\[m\]=max\{c\[i-1\]\[m-w\[i\]\]+pi , c\[i-1\]\[m\]\}

根据上式，对物体个数及背包重量进行递推，列出一个表格（见下表），当逐步推出表中每个值的大小，那个最大价值就求出来了。推导过程中，注意一点，最好逐行而非逐列开始推导，先从编号为1的那一行，推出所有c\[1\]\[m\]的值，再推编号为2的那行c\[2\]\[m\]的大小。这样便于理解。

>   
> 
> 
> 测试数据：
> 
> 10,3
> 
> 3,4
> 
> 4,5
> 
> 5,6

> c\[i\]\[j\]数组保存了1,2,3号物品依次选择后的最大价值.

这个最大价值是怎么得来的呢?从背包容量为0开始,1号物品先试,0,1,2,的容量都不能放.所以置0,背包容量为3则里面放4.这样,这一排背包容量为4,5,6,....10的时候，最佳方案都是放4.假如1号物品放入背包.则再看2号物品.当背包容量为3的时候，最佳方案还是上一排的最价方案c为4.而背包容量为5的时候，则最佳方案为自己的重量5.背包容量为7的时候，很显然是5加上一个值了。加谁??很显然是7-4=3的时候.上一排 c3的最佳方案是4.所以。总的最佳方案是5+4为9.这样.一排一排推下去。最右下放的数据就是最大的价值了。(注意第3排的背包容量为7的时候,最佳方案不是本身的6.而是上一排的9.说明这时候3号物品没有被选.选的是1,2号物品.所以得9.)

![Center][]

C语言代码如下所示：

#include <iostream>
 using namespace std;
 
 #ifndef STONE_NUM
 #define STONE_NUM 3 //定义石头数量
 #endif
 
 #ifndef BACKPACK_SPACE
 #define BACKPACK_SPACE 10
 #endif
 
 int main(int argc, const char * argv[]) {
     int value[BACKPACK_SPACE+1] = {0};
     int stoneSpace[STONE_NUM],stoneValue[STONE_NUM];
     for (int i = 0; i < STONE_NUM; i++) {
         scanf("%d %d", &stoneSpace[i], &stoneValue[i]);
         for (int j = BACKPACK_SPACE; j > 0; j--) {
             if (j >= stoneSpace[i] && value[j] < value[j-stoneSpace[i]] + stoneValue[i]) {
                 value[j] = value[j-stoneSpace[i]] + stoneValue[i];
             }
         }
     }//以上代码几乎无变化，只是存储是数组存储了。
     for (i = 0; i <= BACKPACK_SPACE; i++) {
         printf("%d   ", value[i]);
     }//打印value数组，这里面存放的是，所有物品在背包只有空间i的时候，达到的最大总价值。
 	printf("\n");
 
 
     int backPackSpace = BACKPACK_SPACE;// 得到背包空间
     while (value[backPackSpace] == value[backPackSpace-1]) {
         backPackSpace--;//假如背包价值和背包空间-1的时候价值相同，空间 -1
     }//找到一共使用了多少空间
 	printf("采用的 背包编号为： ");
     for (i = STONE_NUM-1; i >= 0; i--) {
         if (value[backPackSpace] == value[backPackSpace-stoneSpace[i]] + stoneValue[i]) { //假如减去当前物品的空间，总价值刚好和物品的价值相等，说明此物品被放入了。
             printf("%d\t", i+1);//打印这个物品。i+1是因为物品的下标是从0开始的。
             backPackSpace = backPackSpace - stoneSpace[i]; //背包放入了这个物品，自然空间减少了。
         }
     }
 	printf("\n");
     return 0;
 }

（[http://blog.csdn.net/fg2006/article/details/6766384?reload][http_blog.csdn.net_fg2006_article_details_6766384_reload]）

[Center]: /images/20220731/1ccbd28bbc6841c89f626c601c9d0d34.png
[http_blog.csdn.net_fg2006_article_details_6766384_reload]: http://blog.csdn.net/fg2006/article/details/6766384?reload