徐州有办网站的地方吗,建筑设计网上接单,合肥互联网公司,福建 专业网站建设公司0/1背包问题
1.二维数组解法
题目描述#xff1a;有一个容量为m的背包#xff0c;还有n个物品#xff0c;他们的重量分别为w1、w2、w3.....wn#xff0c;他们的价值分别为v1、v2、v3......vn。每个物品只能使用一次#xff0c;求可以放进背包物品的最大价值。
输入样例…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个物品背包容量为jdp[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的最优解
先放的i2的物品然后看剩余重量能容纳的上一行的局部最优解。最后还要判断是否这个最优解比上一行同一列的最优解更大如果更大就更新状态否则就继承状态。
- j1;dp[2][1]0; 继承上一行的状态
- j2;dp[2][2]0; 01,继承上一行的状态
- j3;dp[2][3]3dp[2][0]3 ,31,更新状态使dp[2][3]3;
- j4;dp[2][4]3dp[2][1]3同样状态更新
- j5;dp[2][5]3dp[1][2]4,41 状态更新。
后面也是同理。 再看第三行
j从零到三无法当下第三个物品所以此时的最优解依然是前两个物品最优选择的最优解依旧继承上一行的状态。
然后从第4列开始物品3就可以被放下
- j4,dp[3][4]5dp[2][0]5,53,状态更新
- j5,dp[3][5]5dp[2][1]5,54,状态更新
- j6,dp[3][6]5dp[2][2]6,64,状态更新 我想你聪明如你已经看到规律了接着写出第4行 所以得出来全局的最优解就是12
下面来看代码
#includeiostream
#includealgorithmusing namespace std;//学校的IDE有点老好像不支持algorithm里的max
int max(int x,int y)
{return xy?x:y;
}int m,n;
int dp[30][30]{0};//初始化全部设置为0
int w[30];//重量
int v[30];//价值
//0/1背包问题
int main()
{cinmn;int i0,j0;//输入w,vfor(i1;in;i){cinw[i]v[i];}//主要的循环体for(i1;in;i)//物品编号遍历{for(j1;jm;j)//背包重量遍历{if(jw[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]);}}}coutdp[n][m]endl;return 0;
} 2.一维数组滚动解法
我们注意到二维数组的解法的时间复杂度是m*n空间复杂度是m*n
而暴力求解的时间复杂度是2^n空间复杂度也是m*n
二维数组法确实优化的时间复杂度但是空间复杂度却和暴力一样因此便有了一维数组滚动解法来进一步优化。 我们在上面的分析中一步步的更新局部最优解最终得到所求的最优解。但是有时候并没有更新元素而是继承上一行的最优解那么是不是就可以只用一个一维数组来存储第i行的最优解然后需要更新的时候更新一下就可以了。 这时候我们就可以把原有的代码稍作修改
#includeiostream
#includealgorithmusing namespace std;//学校的IDE有点老好像不支持algorithm里的max
int max(int x,int y)
{return xy?x:y;
}int m,n;
int dp[30]{0};//初始化全部设置为0
int w[30];//重量
int v[30];//价值
//0/1背包问题
int main()
{cinmn;int i0,j0;//输入w,vfor(i1;in;i){cinw[i]v[i];}//主要的循环体for(i1;in;i){for(jm;jw[i];j--)//从最右边遍历后面的多重背包是从做左到右遍历注意区分。{dp[j]max(dp[j],dp[j-w[i]]v[i]);}}coutdp[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]的同层位置的最优解同层是因为物品个数没有限制这样就可以完成叠加。
二维数组法
来看代码
#includeiostream
#includealgorithmusing namespace std;int m,n;
int dp[30][30]{0};
int w[30];
int v[30];
//完全背包问题
int main()
{int i,j;//输入mncinmn;// 输入wvfor(i1;in;i){cinw[i]v[i];} //主要循环体 for(i1;in;i){for(j1;jm;j){//完全背包要先继承上一层状态dp[i][j]dp[i-1][j];if(jw[i]){dp[i][j]max(dp[i][j],dp[i][j-w[i]]v[i]);} }}coutdp[n][m]endl;return 0;
}一维数组滚动解法
这个解法同样也是为了降低空间复杂度 所以以同样的方法优化一下代码
#includeiostream
#includealgorithmusing namespace std;int m,n;
int dp[30]{0};
int w[30];
int v[30];
//完全背包问题
int main()
{int i,j;//输入mncinmn;// 输入wvfor(i1;in;i){cinw[i]v[i];} //主要循环体 for(i1;in;i){for(jw[i];jm;j){dp[j]max(dp[j],dp[j-w[i]]v[i]);}}coutdp[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背包问题
这个方法比较容易想到就不过多赘述了 看代码
#includeiostream
#includealgorithmusing namespace std;int m,n;
int dp[30]{0};
int w[30];
int v[30];
int c[30];
int main()
{int i,j,k;//输入mncinmn;//输入wvc数量 for(i1;in;i){cinw[i]v[i]c[i];} for(i1;in;i){for(k1;kc[i];k)//多次模拟0/1背包 {for(jm;jw[i];j--)//一维滚动法 {dp[j]max(dp[j],dp[j-w[i]]v[i]); }}}for(i1;im;i)//这里直接电脑验证了 {coutdp[i] ;}coutendl;coutdp[m];return 0;} //10 3 2 1 6 6 10 3 3 6 3特别感谢某站T_zhao 老师的讲解讲的很明白。
