01背包算法

浏览数：42 / 时间：2015年06月08日

转：01背包问题

动态规划的基本思想：

将一个问题分解为子问题递归求解，且将中间结果保存以避免重复计算。通常用来求最优解，且最优解的局部也是最优的。求解过程产生多个决策序列，下一步总是依赖上一步的结果，自底向上的求解。

动态规划算法可分解成从先到后的4个步骤：

1. 描述一个最优解的结构，寻找子问题，对问题进行划分。

2. 定义状态。往往将和子问题相关的各个变量的一组取值定义为一个状态。某个状态的值就是这个子问题的解（若有k个变量，一般用K维的数组存储各个状态下的解，并可根据这个数组记录打印求解过程。）。

3. 找出状态转移方程。一般是从一个状态到另一个状态时变量值改变。

4.以“自底向上”的方式计算最优解的值。

5. 从已计算的信息中构建出最优解的路径。(最优解是问题达到最优值的一组解)

其中步骤1~4是动态规划求解问题的基础，如果题目只要求最优解的值，则步骤5可以省略。

背包问题

01背包: 有N件物品和一个重量为M的背包。（每种物品均只有一件）第i件物品的重量是w[i]，价值是p[i]。求解将哪些物品装入背包可使价值总和最大。

完全背包: 有N种物品和一个重量为M的背包，每种物品都有无限件可用。第i种物品的重量是w[i]，价值是p[i]。求解将哪些物品装入背包可使这些物品的费用总和不超过背包重量，且价值总和最大。

多重背包: 有N种物品和一个重量为M的背包。第i种物品最多有n[i]件可用，每件重量是w[i]，价值是p[i]。求解将哪些物品装入背包可使这些物品的费用总和不超过背包重量，且价值总和最大。

01背包问题：

这是最基础的背包问题，特点是：每种物品仅有一件，可以选择放或不放。

用子问题定义状态：即c[i][v]表示前i件物品恰放入一个重量为m的背包可以获得的最大价值。则其状态转移方程便是：

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

这个方程非常重要，基本上所有跟背包相关的问题的方程都是由它衍生出来的。所以有必要将它详细解释一下：“将前i件物品放入重量为m的背包中”这个子问题，若只考虑第i件物品的策略（放或不放），那么就可以转化为一个只牵扯前i-1件物品的问题。如果不放第i件物品，那么问题就转化为“前i-1件物品放入容量为v的背包中”，价值为c[i-1][m]；如果放第i件物品，那么问题就转化为“前i-1件物品放入剩下的重量为m-w[i]的背包中”，此时能获得的最大价值就是c[i-1][m-w[i]]再加上通过放入第i件物品获得的价值p[i]。

代码：

 1 #include <iostream>
 2 #include <algorithm>
 3 #include <cstdio>
 4 #include <cstring>
 5 #include <queue>
 6 #include <cmath>
 7 #define clr(a,b) memset(a,b,sizeof(a))
 8 #define INF 0x7f7f7f7f
 9 #define M 1050
10 using namespace std;
11 int V[200][200];//前i个物品装入容量为j的背包中获得的最大价值
12 int max(int a,int b)
13 {
14     if(a>=b)
15         return a;
16     else return b;
17 }
18 
19 int KnapSack(int n,int w[],int v[],int x[],int C)
20 {
21     int i,j;
22     for(i=0; i<=n; i++)
23         V[i][0]=0;
24     for(j=0; j<=C; j++)
25         V[0][j]=0;
26     for(i=1; i<=n; i++)
27         for(j=1; j<=C; j++)
28             if(j<w[i])
29                 V[i][j]=V[i-1][j];
30             else
31                 V[i][j]=max(V[i-1][j],V[i-1][j-w[i]]+v[i]);
32     j=C;
33     for(i=n-1; i>=0; i--)  
34     {
35         if(V[i][j]>V[i-1][j]) //既然if成立说明该物品被选择了。
36         {
37             x[i]=1;
38             j=j-w[i];
39         }
40         else
41             x[i]=0;
42     }
43     printf("选中的物品是:\n");
44     for(i=0; i<n; i++)
45         printf("%d ",x[i]);
46     printf("\n");
47     return V[n-1][C];
48 
49 }
50 
51 int main()
52 {
53     int s;//获得的最大价值
54     int w[15];//物品的重量
55     int v[15];//物品的价值
56     int x[15];//物品的选取状态
57     int n,i;
58     int C;//背包最大容量
59     n=5;
60     memset(V,0,sizeof(V));
61     printf("请输入背包的最大容量:\n");
62     scanf("%d",&C);
63     printf("输入物品数:\n");
64     scanf("%d",&n);
65     printf("请分别输入物品的重量:\n");
66     for(i=0; i<n; i++)
67         scanf("%d",&w[i]);
68     printf("请分别输入物品的价值:\n");
69     for(i=0; i<n; i++)
70         scanf("%d",&v[i]);
71     s=KnapSack(n,w,v,x,C);
72     printf("最大物品价值为:\n");
73     printf("%d\n",s);
74 }
75 /*
76 10
77 5
78 3 4 5 3 2
79 3 2 6 4 3
80 */