背包问题 dp

= =

所谓背包问题嘛，就是给你个容量一定的包，给你一些有价值的东西，把东西放入包里价值最大。

参考来源：http://blog.csdn.net/insistgogo/article/details/8579597

我们用w[i],v[i]分别表示第i件物品的重量,价值。

这里我们讨论用动态规划解该问题：

子问题：va[i][j]表示前i件物品，放到容量为j的包里所得最大值

状态转移方程：va[i][j]=max(va[i-1][j],va[i-1][j-w[i]])

因而我们可以很快得到代码：复杂度:O(W*N)

 1 #include <iostream>
 2 #include <cstring>
 3 #include <algorithm>
 4 using namespace std;
 5 
 6 const int N =100;
 7 
 8 int va[N][N];
 9 int weight=5,num=3;
10 int v[N]={0,5,10,20};
11 int w[N]={0,3,2,2};
12 //int f[N];
13 
14 void datecal1(int weight,int num)
15 {
16     for(int j=1;j<=weight;j++)
17     {
18         for(int i=1;i<=num;i++)
19         {
20             if(w[i]>j)
21                 va[i][j]=va[i-1][j];
22             else
23                 va[i][j]=max(va[i-1][j-w[i]]+v[i],va[i-1][j]);
24         }
25     }
26 }
27 
28 void datecal2(int weight,int mum)
29 {
30     for(int i=1;i<=num;i++)
31     {
32         for(int j=1;j<=weight;j++)
33         {
34             if(w[i]>j)
35                 va[i][j]=va[i-1][j];
36             else
37                 va[i][j]=max(va[i-1][j],va[i-1][j-w[i]]+v[i]);
38         }
39     }
40 }
41 
42 void showva()
43 {
44     for(int i=0;i<=num;i++)
45     {
46         for(int j=0;j<=weight;j++)
47         {
48             cout<<va[i][j]<<"  ";
49         }
50         cout<<endl;
51     }
52 }
53 
54 int main()
55 {
56     memset(va,0,sizeof(va));
57     datecal1(weight,num);
58     showva();
59     cout<<endl;
60     memset(va,0,sizeof(va));
61     datecal2(weight,num);
62     showva();
63     return 0;
64 }

关于两个函数，我测试了一下，结果是一样的，因为va[i][j]所代表的值是一样的

下面优化了一下储存状态的数组：

即将状态转移方程改为：f[j]=max(f[j],f[j-w[i]]+w[i])

我们用一维数组储存了价值，而且是用逆序枚举的容量，关于为什么，可以看一下原博客

 1 #include <iostream>
 2 #include <cstring>
 3 #include <algorithm>
 4 using namespace std;
 5 
 6 const int N =100;
 7 
 8 int weight=5,num=3;
 9 int v[N]={0,5,10,20};
10 int w[N]={0,3,2,2};
11 int f[N];
12 
13 void datecal3(int weight,int num)
14 {
15     for(int i=1;i<=num;i++)
16     {
17         for(int j=weight;j>=w[i];j--)
18         {
19             f[j]=max(f[j],f[j-w[i]]+v[i]);
20         }
21     }
22     cout<<f[weight]<<endl;
23 }

即我们使用一维数组储存前一个数组的状态，但缺点和最大子序和里面sum替换数组s[]一样，缺失了之前的状态的最大和,仅仅得到了最终结果

以上是现在学习的0-1背包问题，关于其他背包问题我会在后面继续学习了再完成该博,先搁置一下

　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　2016.4.26