动态规划01背包

目录

01背包问题简介详细说明状态转移方程详解举例代码块测试结果

---

01背包问题简介

0-1背包问题：给定n种物品和一背包。物品i的重量是wi，其价值为vi，背包的容量为C。问：应该如何选择装入背包的物品，使得装入背包中的物品的总价值最大？ 在选择装入背包的物品时，对每种物品i只有两种选择，即装入背包或不装入背包。不能将物品i装入背包多次，也不能只装入部分的物品i。因此，该问题称为0-1背包问题。

---

详细说明

01背包的状态转换方程 c[i,j] = max{ c[i-1,j-w[i]]+p[i]( j >= w[i] ), c[i-1,j] } c[i,j]表示在前i件物品中选择若干件放在承重为 j 的背包中，可以取得的最大价值。

---

问题分析：令c(i,j)表示在前i(1<=i<=n)个物品中能够装入容量为就j(1<=j<=C)的背包中的物品的最大价值，则可以得到如下的动态规划函数:

(1)

c(i,0)=c(0,j)=0

(2)

c(i,j)=c(i-1,j) （j小于wi） c(i,j)=max{c(i-1,j) ,c(i-1,j-wi)+pi) } ( j>wi)

(1)式表明：如果第i个物品的重量大于背包的容量，则装入前i个物品得到的最大价值和装入前i-1个物品得到的最大价都是相同的，即物品i不能装入背包。c(i，0)=c（0，j）=0表示第i个物体装入容量为0的背包或者第0个物体装入容量为j的背包的价值都是0 (2)式表明，如果第i个物品的质量小于背包的容量，则会有一下两种情况：

（a）. 如果把i个物品装入背包，则背包物品的价值等于第i-1个物品装入容量为j-wi的背包中的价值加上第i个物品的价值p。

（b）.如果第i个物品没有装入背包，则背包中物品的价值就等于把前i-1个物品装入容量为j放入背包中所取得的价值。显然取2者中价值最大的作为前i个物品物品装入容量为j放入背包中的最优值。

---

状态方程详解

由表达式中各个符号的具体含义可得：

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

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

c[i][j]:第i个物体放入容量为j的背包的最大价值

c[i-1][j]:前i-1个物体放入容量为j的背包的最大价值

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

因此状态方程：c[i][j]= max{c[i-1][j],c[i-1][j-w[i]]+p[i]} 解释：第一种是第i件放不进去，这时所得价值为c[i-1][j];第二种是第i件放进去，这时所得价值为c[i-1][j-w[i]]（第二种是什么意思?就是如果第i件放进去，那么容量j-w[i]里就要放入前i-1件物品）。最后比较第一种和第二种所的价值的大小，哪种相对大，c[i][j]的值就是哪种

---

举例

有编号分别为a,b,c,d,e的五件物品，它们的重量分别是2,2,6,5,4，它们的价值分别是6,3,5,4,6，现在给你个承重为10的背包，如何让背包里装入的物品具有最大的价值总和？ 只要你能通过找规律手工填写出上面这张表就算理解了01背包的动态规划算法。 首先要明确这张表是至底向上，从左到右生成的。 为了叙述方便，用e2单元格表示e行2列的单元格，这个单元格的意义是用来表示只有物品e时，有个承重为2的背包，那么这个背包的最大价值是0，因为e物品的重量是4，背包装不了。 对于d2单元格，表示只有物品e，d时,承重为2的背包,所能装入的最大价值，仍然是0，因为物品e,d都不是这个背包能装的。 同理，c2=0，b2=3,a2=6。 对于承重为8的背包，a8=15,是怎么得出的呢？ 根据01背包的状态转换方程，需要考察两个值，

一个是c[i-1,j],对于这个例子来说就是b8的值9，另一个是c[i-1,j-wi]+Pi；

在这里，

c[i-1,j]表示我有一个承重为8的背包，当只有物品b,c,d,e四件可选时，这个背包能装入的最大价值 c[i-1,j-wi]表示我有一个承重为6的背包（等于当前背包承重减去物品a的重量），当只有物品b,c,d,e四件可选时，这个背包能装入的最大价值 c[i-1,j-wi]就是指单元格b6,值为9，Pi指的是a物品的价值，即6 由于c[i-1,j-wi]+pi = 9 + 6 = 15 大于c[i-1,j] = 9，所以物品a应该放入承重为8的背包

---

代码块

#include<stdio.h> #include<stdlib.h> #define max(a,b) (((a)>(b))?(a):(b)) int v[200][200]; int KnapSack(int c, int *w, int *p, int *x, int n) { int i, j; for (i = 0; i <= n; i++) { v[i][0] = 0; //第i个物体放入容量为0的背包中价值为0 } for (j = 0; j <= c;j++) { v[0][j] = 0; //第0个物体放入容量为j的背包中价值为0 } for (i = 1; i <= n ; i++) { for (j = 0; j <= c; j++) { if (w[i] > j) //表示第i个物体不能放入背包，因此背包的价值等于前i-1个物体放入背包总量的价值 { v[i][j] = v[i - 1][j]; } else //表示第i个物体可以放入背包，因此背包的价值等于前i-1个物体放入(背包总量-第i个物体质量)的总量中的价值加上 { //第i个价值之和 与v[i-1][j]的最大者 v[i][j] = max(v[i - 1][j], v[i - 1][j - w[i]] + p[i]); } } } j = c; for (i = n ; i >= 1; i--) { if (v[i][j] > v[i - 1][j])//前i个物体放入容量为j的背包中的价值比前i-1个物体放入容量为j的背包中的价值大 { x[i] = 1; //表示这个物体被放入背包 j = j - w[i];//现总容量=原总容量-第i个物体所占的容量 } else { x[i] = 0;//这个物体没有放入背包 } } printf("被选中的物品是(1是选中,0是未选中):\n"); for (i = 1; i <= n ; i++) { printf("%d(物体%d) ", x[i],i); } printf("\n"); return v[n ][c]; } int main(void) { int n, i; int s, c; printf("有几个物体:\n"); scanf("%d", &n); int *w; w = (int *)malloc((n+1)*sizeof(int)); int *p; p = (int *)malloc((n+1)*sizeof(int)); int *x; x = (int *)malloc((n+1)*sizeof(int)); printf("请输入物体1--物体%d的重量:\n",n); for (i = 1; i <= n; i++) { scanf("%d", &w[i]); } printf("请输入物体1--物体%d的价值:\n",n); for (i = 1; i <= n; i++) { scanf("%d", &p[i]); } printf("请输入背包的最大容量:\n"); scanf("%d", &c); s = KnapSack(c, w, p, x, n); printf("最大的物品价值和为:\n"); printf("%d", s); system("pause"); return 0; }

---

测试结果