动态规划之背包问题

0/1背包问题

1.二维数组解法

题目描述：有一个容量为m的背包，还有n个物品，他们的重量分别为w1、w2、w3.....wn，他们的价值分别为v1、v2、v3......vn。每个物品只能使用一次，求可以放进背包物品的最大价值。

输入样例：

10 4

2 1

3 3

4 5

7 9

输出样例：

12

解：

符号描述：i表示第i个物品，背包容量为j，dp[i][j]表示从下标为0到i，背包容量为j时任意选取物品所得价值的最大值。所以全局的最优解就是dp[m][n]

背包问题和函数的递归很像，只不过函数递归时从结果去接近边界，而背包问题是从边界出发，从小问题逐步去接近最终所要求的最优解。

先创建一个二维数组

可以看到当背包容量为零，或者可选物品为0时，他的局部最优解都是0

然后从每一行的左到右开始遍历（具体是为什么可以自己试一试）

- 当背包容量为1时由于第一个物品的重量为2无法放进去，所以dp[1][1]=0;

- 当背包容量为2时可以放进第一个物品，dp[2][1]=1;

- 当背包容量大于2时，后续的最大价值都是1；

接着看第二行，这个第二行的含义就是当背包物品容量从1到j变化时，任意选物品1-2的最优解

先放的i=2的物品，然后看剩余重量能容纳的上一行的局部最优解。最后还要判断是否这个最优解比上一行同一列的最优解更大，如果更大就更新状态，否则就继承状态。

- j=1;dp[2][1]=0; 继承上一行的状态

- j=2;dp[2][2]=0; 0<1,继承上一行的状态

- j=3;dp[2][3]=3+dp[2][0]=3 ,3>1,更新状态使dp[2][3]=3;

- j=4;dp[2][4]=3+dp[2][1]=3，同样状态更新

- j=5;dp[2][5]=3+dp[1][2]=4,4>1 状态更新。

后面也是同理。

再看第三行

j从零到三无法当下第三个物品，所以此时的最优解依然是前两个物品最优选择的最优解，依旧继承上一行的状态。

然后从第4列开始，物品3就可以被放下

- j=4,dp[3][4]=5+dp[2][0]=5,5>3,状态更新

- j=5,dp[3][5]=5+dp[2][1]=5,5>4,状态更新

- j=6,dp[3][6]=5+dp[2][2]=6,6>4,状态更新

我想你聪明如你已经看到规律了，接着写出第4行

所以得出来全局的最优解就是12

下面来看代码：

#include<iostream>
#include<algorithm>using namespace std;//学校的IDE有点老，好像不支持algorithm里的max
int max(int x,int y)
{return x>y?x:y;
}int m,n;
int dp[30][30]={0};//初始化全部设置为0
int w[30];//重量
int v[30];//价值
//0/1背包问题
int main()
{cin>>m>>n;int i=0,j=0;//输入w,vfor(i=1;i<=n;i++){cin>>w[i]>>v[i];}//主要的循环体for(i=1;i<=n;i++)//物品编号遍历{for(j=1;j<=m;j++)//背包重量遍历{if(j<w[i])//这个物品无法放进去，继承上一行的状态{dp[i][j]=dp[i-1][j];}else//判断当前最优解与上一行的最优解谁更大{dp[i][j]=max(dp[i-1][j],dp[i-1][j-w[i]]+v[i]);}}}cout<<dp[n][m]<<endl;return 0;
}

2.一维数组滚动解法

我们注意到二维数组的解法的时间复杂度是m*n，空间复杂度是m*n

而暴力求解的时间复杂度是2^n，空间复杂度也是m*n

二维数组法确实优化的时间复杂度，但是空间复杂度却和暴力一样，因此便有了一维数组滚动解法来进一步优化。

我们在上面的分析中，一步步的更新局部最优解，最终得到所求的最优解。但是有时候并没有更新元素而是继承上一行的最优解，那么是不是就可以只用一个一维数组来存储第i行的最优解，然后需要更新的时候更新一下就可以了。

这时候我们就可以把原有的代码稍作修改：

#include<iostream>
#include<algorithm>using namespace std;//学校的IDE有点老，好像不支持algorithm里的max
int max(int x,int y)
{return x>y?x:y;
}int m,n;
int dp[30]={0};//初始化全部设置为0
int w[30];//重量
int v[30];//价值
//0/1背包问题
int main()
{cin>>m>>n;int i=0,j=0;//输入w,vfor(i=1;i<=n;i++){cin>>w[i]>>v[i];}//主要的循环体for(i=1;i<=n;i++){for(j=m;j>=w[i];j--)//从最右边遍历，后面的多重背包是从做左到右遍历注意区分。{dp[j]=max(dp[j],dp[j-w[i]]+v[i]);}}cout<<dp[m]<<endl;return 0;
}

电脑验证

二维数组：

完全背包问题

题目描述：有一个容量为m的背包，还有n个物品，他们的重量分别为w1、w2、w3.....wn，他们的价值分别为v1、v2、v3......vn。每个物品有无限个，求可以放进背包物品的最大价值。

输入样例：10 4 2 1 3 3 4 6 8 10

输出样例：13

完全背包区别于0/1背包就是每个物品的选择没有次数限制。

它们的解题思路的区别在于主要的循环体那，完全背包需要先继承上一层的状态，然后考虑能不能放下，如果不能那这个位置的最优解就是上层位置的最优解，否则就把这个物品放进来，再加上背包容量为j-w[i]的同层位置的最优解（同层是因为物品个数没有限制），这样就可以完成叠加。

二维数组法

来看代码：

#include<iostream>
#include<algorithm>using namespace std;int m,n;
int dp[30][30]={0};
int w[30];
int v[30];
//完全背包问题 
int main()
{int i,j;//输入m，ncin>>m>>n;// 输入w，vfor(i=1;i<=n;i++){cin>>w[i]>>v[i];} //主要循环体 for(i=1;i<=n;i++){for(j=1;j<=m;j++){//完全背包要先继承上一层状态dp[i][j]=dp[i-1][j];if(j>=w[i]){dp[i][j]=max(dp[i][j],dp[i][j-w[i]]+v[i]);} }}cout<<dp[n][m]<<endl;return 0;
}

一维数组滚动解法

这个解法同样也是为了降低空间复杂度

所以以同样的方法优化一下代码：

#include<iostream>
#include<algorithm>using namespace std;int m,n;
int dp[30]={0};
int w[30];
int v[30];
//完全背包问题 
int main()
{int i,j;//输入m，ncin>>m>>n;// 输入w，vfor(i=1;i<=n;i++){cin>>w[i]>>v[i];} //主要循环体 for(i=1;i<=n;i++){for(j=w[i];j<=m;j++){dp[j]=max(dp[j],dp[j-w[i]]+v[i]);}}cout<<dp[m]<<endl;return 0;
}

电脑验证

二维数组法：

一维数组滚动法：

多重背包问题

多重背包问题与前面两个问题的区别也是在物品的数量上，这次它换成了有限个。

题目描述：有一个容量为m的背包，还有n个物品，他们的重量分别为w1、w2、w3.....wn，他们的价值分别为v1、v2、v3......vn，它们的数量分别有c1、c2、c3......cn个，求可以放进背包物品的最大价值。

输入样例：

10 3

2 1 6

6 10 3

3 6 3

输出样例：

转换成传统的0/1背包问题

这个方法比较容易想到，就不过多赘述了

看代码：

#include<iostream>
#include<algorithm>using namespace std;int m,n;
int dp[30]={0};
int w[30];
int v[30];
int c[30];
int main()
{int i,j,k;//输入m，ncin>>m>>n;//输入w，v，c（数量） for(i=1;i<=n;i++){cin>>w[i]>>v[i]>>c[i];} for(i=1;i<=n;i++){for(k=1;k<=c[i];k++)//多次模拟0/1背包 {for(j=m;j>=w[i];j--)//一维滚动法 {dp[j]=max(dp[j],dp[j-w[i]]+v[i]);	 			}}}for(i=1;i<=m;i++)//这里直接电脑验证了 {cout<<dp[i]<<" ";}cout<<endl;cout<<dp[m];return 0;} //10 3 2 1 6 6 10 3 3 6 3

特别感谢某站T_zhao 老师的讲解，讲的很明白。