电子商务网站建设选修课,房屋装修设计app,安卓图形网站建设,如何建立自己的网络销售C算法初级11——01背包问题#xff08;动态规划2#xff09; 文章目录 C算法初级11——01背包问题#xff08;动态规划2#xff09;问题引入0-1背包问题分析0-1背包问题的形式化分析优化 问题引入
辰辰采药
辰辰是个天资聪颖的孩子#xff0c;他的梦想是成为世界上最伟大…C算法初级11——01背包问题动态规划2 文章目录 C算法初级11——01背包问题动态规划2问题引入0-1背包问题分析0-1背包问题的形式化分析优化 问题引入
辰辰采药
辰辰是个天资聪颖的孩子他的梦想是成为世界上最伟大的医师。为此他想拜附近最有威望的医师为师。医师为了判断他的资质给他出了一个难题。医师把他带到一个到处都是草药的山洞里对他说“孩子这个山洞里有一些不同的草药采每一株都需要一些时间每一株也有它自身的价值。我会给你一段时间在这段时间里你可以采到一些草药。如果你是一个聪明的孩子你应该可以让采到的草药的总价值最大。”
如果你是辰辰你能完成这个任务吗
辰辰采药在算法中属于一种很经典的0-1背包问题。更一般的这种问题可以转化为
给定n个物品每个物体有个体积v i和一个价值p i 现有一个容量为V的背包请问如何选择物品装入背包使得获得的总价值最大
0-1背包问题分析
0-1背包问题描述给定n个物品每个物体有个体积v i和一个价值p i 现有一个容量为V的背包请问如何选择物品装入背包使得获得的总价值最大
基本思路 考虑到现在我们能做的决策只有对于每个物品的“选”与“不选”。所以这个问题就是
以“将每一个物品依次放入背包”划分不同阶段而对于每个物品的“选与不选”就是不同决策
考虑到所有的放置前i个物品的方案数可以分为两类
一个是放第i个物品一个是不放第i个物品
所以下面我们分这两种情况来讨论。因为在决策的过程中变化的是当前所在的阶段以及容量的剩余大小。 所以我们维护一个二维状态f[i,j], 来表示前i个物品放到体积为j的背包里可以得到的最大价值。
首先考虑容量为任意值j时将前i个物品放入背包的情况。 所以状态转移方程为 f [ i ] [ j ] m a x { f [ i − 1 , j ] , p [ i ] f [ i − 1 ] [ j − v [ i ] } f[i][j]max\{f[i-1,j],p[i]f[i-1][j-v[i]\} f[i][j]max{f[i−1,j],p[i]f[i−1][j−v[i]}
0-1背包问题的形式化分析
使用动态规划解决问题需要明确状态设计、转移方程、初始状态和转移方向四个方面。
那现在让我们来明确一下该0-1背包问题中的动态规划四要素
状态 用f[i][j]表示前i个物品放在空间为j的背包里能获得的最大收益。转移方程 因为每一个阶段有至多两种选择所以需要分别计算两种选择的收益后取较大值。
f[i][j] f[i - 1][j] // j v[i]表示装不下第i个物品
f[i][j] max(f[i - 1][j], f[i - 1][j - v[i]] p[i]); // otherwise初始状态 在一个物品都没放的时候无论背包大小多少总价值都是0即
f[0][j] 0 // 0 j V转移方向 观察转移方程发现要想保证等式右边的状态一定比左边的状态先算出来只需要保证i从小到大计算即可。 最终该问题的答案就是f[n,V]。这样0-1背包问题就可以使用动态规划来解决
代码
# include bits/stdc.h
using namespace std;# define N 1002
int n3;
int V 70;
vectorint v {0,71,69,1};//体积
vectorint p {0,100,1,2};//价值
// 第0位置为0不参与计算便于与后面的下标进行统一
int f[N][N];int main()
{for(int j0;jV;j)f[0][j]0;for(int i1;in;i){if(v[i]V)continue;for(int j0;jV;j){if(jv[i])f[i][j]f[i-1][j];elsef[i][j]max(f[i-1][j],f[i-1][j-v[i]]p[i]);}}coutf[n][V]endl;
}动态规划的主要工作就是算出不同状态下的结果然后用相应维数的数组保存。
所以整个动态规划的过程就是一个”填表“的过程。
优化 滚动数组优化 因为整个动态规划的过程就是一个填表的过程如下图 而在本题中填表的顺序就是填完上一行然后填下一行。而且我们发现下一行的状态只会用到上一行的状态来转移。所以当我们在计算第i行时其实前i−2行的状态就都没必要保留了。所以我们可以用一种类似于”踩石头过河“的思想。
试想如果我们有一些石头想利用这些石头过河。
如果石头的数量很多那么最方便的方法就是用这些石头铺一道石头路这样我们就可以顺利过河。这就相当于我们可以开很充足的数组然后把计算的每个阶段都存在数组里。
但如果我们只有两块石头就过不了河了吗不是的。我们可以用下图的方法一边走一边挪动石头这样也可以顺利过河。 在空间优化的方法中有一种很常见就是利用过河的思想。这种方法叫做滚动数组。在整个算法过程中我们只用2×V的数组f[2][V]来记录状态。其中所有奇数行的状态填入f[1][j]中所有偶数行的状态填入f[0][j]中如下图
# include bits/stdc.h
using namespace std;# define N 1002
int n3;
int V 70;
vectorint v {0,71,69,1};//体积
vectorint p {0,100,1,2};//价值
// 第0位置为0不参与计算便于与后面的下标进行统一
int f[2][N];//f[i][j]表示前i个物品体积为j的最大价值int main()
{for(int i1;in;i){for(int j0;jV;j){if(jv[i])f[i1][j] f[(i-1)1][j];elsef[i1][j] max(f[(i-1)1][j],f[(i-1)1][j-v[i]]p[i]);}}coutf[n1][V]endl;return 0;
}算法优化2 —— 优化到一维数组 那么我们可不可以再进一步优化空间使得只用一个一维数组就能解决整个问题了呢
想到之前“踩石头过河”的类比我们可能会觉得不太可能。但是如果我们进一步分析整个表的填写如下图 会发现下一行的某个状态正好是由它上面的元素以及左上方的某个元素转移而来。所以我们需要保证当计算黄色状态时上面两个绿色状态没有被覆盖掉。所以当我们计算第i行时完全可以将j从大到小枚举这样在计算状态f(i,j)之前数组f[j]中存储的是状态f[i−1,j]更新完以后 f[j]中存的状态就是f[i,j]了。如下图
# include bits/stdc.h
using namespace std;# define N 1002
int n3;
int V 70;
vectorint v {0,71,69,1};//体积
vectorint p {0,100,1,2};//价值
// 第0位置为0不参与计算便于与后面的下标进行统一
int f[N];int main()
{for(int i1;in;i){for(int jV;jv[i];j--){f[j] max(f[j],f[j-v[i]]p[i]);}}coutf[V]endl;return 0;
}
