学校网站建设及使用,网页设计欣赏分析,品牌营销策划,安次区建设局网站Halo#xff0c;这里是Ppeua。平时主要更新C语言#xff0c;C#xff0c;数据结构算法......感兴趣就关注我吧#xff01;你定不会失望。 #x1f308;个人主页#xff1a;主页链接 #x1f308;算法专栏#xff1a;专栏链接 我会一直往里填充内容哒#xff01; … Halo这里是Ppeua。平时主要更新C语言C数据结构算法......感兴趣就关注我吧你定不会失望。 个人主页主页链接 算法专栏专栏链接 我会一直往里填充内容哒 LeetCode专栏专栏链接 目前在刷初级算法的LeetBook 。若每日一题当中有力所能及的题目也会当天做完发出 代码仓库Gitee链接 点击关注收获更多优质内容 目录
DP:
题目:01背包问题
题解:
代码实现:
优化:
代码实现:
题目:完全背包
题解:
代码实现:
优化:
代码实现:
优化
代码实现: 完结撒花 好**难啊整抑郁了
DP: DP有这样的一个分析方法 题目:01背包问题 有 N 件物品和一个容量是 V 的背包。每件物品只能使用一次。 第 i件物品的体积是 vi价值是 wi 求解将哪些物品装入背包可使这些物品的总体积不超过背包容量且总价值最大。 输出最大价值。 输入格式 第一行两个整数NV用空格隔开分别表示物品数量和背包容积。 接下来有 N行每行两个整数 vi,wi用空格隔开分别表示第 i件物品的体积和价值。 输出格式 输出一个整数表示最大价值。 数据范围 0N,V≤1000 0vi,wi≤1000 输入样例 4 5
1 2
2 4
3 4
4 5输出样例 8题解:
分析01背包问题的特点有N件物品背包容积是V每件物品只能拿0或不拿1所以称为01背包问题.
将问题分析,当决定第i件拿与不拿的时候,表达式为:此时背包价值max(背包没拿第i件物品的价值,拿了第i件物品的价值)
所以这里的状态表示的集合为:从前i件物品拿,且总体积不超过j 状态表示的属性为:最大值 状态计算为f[i][j],其中i为第几件物品,j为此时背包的容量
其中不选第i件物品总价值,就为前一个相同容量的背包中的价值 因为直接计算选第i件物品比较难计算,所以我们将选第i件物品的价值转换为,不选第i件物品的价值,并令其背包容积减去第i件物品的v再加上其价值w 所以我们的状态方程就为:f[i][j]max(f[i-1],f[i-1][j-v]w)
代码实现:
#includeiostream
using namespace std;
int n, m;
const int N 1010;
int v[N], w[N];
int f[N][N];
int solution1()
{cin n m;for (int i 1; i n; i)cin v[i] w[i];for (int i 0; i m; i)f[0][i] 0;//一件物品都没选 0-m的容积下价值都为0for (int i 1; i n; i){for (int j 0; j m; j){f[i][j] f[i - 1][j];if (j v[i])f[i][j] max(f[i][j], f[i - 1][j - v[i]] w[i]);//在拿i-1件物品其容量为j-vi时放入物品的最大值 }}cout f[n][m];
} 优化:
观察.f[i][j]的变换形式,每次计算只用到了上一层i,j,所以我们可以将i这一维给删了,变成这种形式
直接将[i]删了
int n, m;
const int N 1010;
int v[N], w[N];
int f[N];
int main()
{cin n m;for (int i 1; i n; i)cin v[i] w[i];for (int i 0; i m; i)f[i] 0;//一件物品都没选 0-m的容积下价值都为0for (int i 1; i n; i){for (int j v[i]; jm; j){f[j] max(f[j], f[j - v[i]] w[i]);//滚动数组优化从后向前遍历这样第一个的结果用到的是上一层的数据}}cout f[m];
}但观察此时的状态方程.
f[j-v[i]]w[i],用到的是这一层已经计算的数据(因为j是从小开始算的,也就是说从小的j开始就会把上一次计算的j给覆盖了,而后面要用到的是上面一层i-1的数据,而不是i)
所以我们为了避免这种情况,使用i-1的数据,我们从后往前遍历,这样每一次计算j时,用的就是i-1层的数据,与上文所述一致
代码实现:
int n, m;
const int N 1010;
int v[N], w[N];
int f[N];
int main()
{cin n m;for (int i 1; i n; i)cin v[i] w[i];for (int i 0; i m; i)f[i] 0;//一件物品都没选 0-m的容积下价值都为0for (int i 1; i n; i){for (int j m; j v[i]; j--){f[j] max(f[j], f[j - v[i]] w[i]);//滚动数组优化从后向前遍历这样第一个的结果用到的是上一层的数据}}cout f[m];
}
题目:完全背包 有 N种物品和一个容量是 V 的背包每种物品都有无限件可用。 第 i种物品的体积是 vi价值是 wi。 求解将哪些物品装入背包可使这些物品的总体积不超过背包容量且总价值最大。 输出最大价值。 输入格式 第一行两个整数NV用空格隔开分别表示物品种数和背包容积。 接下来有 N行每行两个整数 vi,wi用空格隔开分别表示第 i 种物品的体积和价值。 输出格式 输出一个整数表示最大价值。 数据范围 0N,V≤1000 0vi,wi≤1000 输入样例 4 5
1 2
2 4
3 4
4 5输出样例 10 题解:
完全背包问题是01背包问题的升级版.每件物品不再只能拿一件,而可以无限拿(在容量允许的情况下) 将问题分析,当决定第i件拿K件,表达式为:此时背包价值max(背包没拿第i件物品的价值,拿了K*第i件物品的价值)
所以这里的状态表示的集合为:从前i件物品拿K件,且总体积不超过j 状态表示的属性为:最大值 状态计算为f[i][j],其中i为第几件物品,j为此时背包的容量
其中不选第i件物品总价值,就为前一个相同容量的背包中的价值 因为直接计算拿第i件k个比较难计算,所以我们将选第i件物品的价值转换为,不选第i件物品的价值,并令其背包容积减去第i件物品的K*v再加上其价值K*w 代码实现:
#include algorithm
#includeiostream
using namespace std;
int n, m;
const int N 1010;
int v[N], w[N];
int f[N][N];
int main()
{for (int i 1; i n; i)cin v[i] w[i];for (int i 0; i m; i)f[0][i] 0;//一件物品都没选 0-m的容积下价值都为0for(int i1;in;i){for(int j0;jm;j){for(int k0;k*v[i]j;k){f[i][j]f[i-1][j];if(jk*v[i])f[i][j]max(f[i][j],f[i-1][j-k*v[i]]k*w[i]);}}}coutf[n][m];
}
这和01背包问题的朴素做法几乎一模一样,但这里的时间复杂度为n^3,所以我们得优化一下,不然就TLE了 优化: 对于f[i,j-v]的含义是:将JK*V时,我们先将第i个物品放入背包,之后再去找当前容量下能放入的最大价值的东西,之后再加上w,这时候就可以不用考虑具体放几件了,
最后也就变成了f[i][j]Max(f[i-1][j],f[i][j-v]w)
代码实现:
#include algorithm
#includeiostream
using namespace std;
int n, m;
const int N 1010;
int v[N], w[N];
int f[N][N];
int main()
{cinnm;for (int i 1; i n; i)cin v[i] w[i];for (int i 0; i m; i)f[0][i] 0;//一件物品都没选 0-m的容积下价值都为0for(int i1;in;i){for(int j0;jm;j){f[i][j]f[i-1][j];if(jv[i])f[i][j]max(f[i][j],f[i][j-v[i]]w[i]);//表示已经选入第i层 }}coutf[n][m];
}
优化
因为还是N^2,观察这个表达式,和01背包问题很想,且也只用到了i-1层 所以可以用滚动数组优化,删掉一维即可,因为这里计算max的时候用的式i 所以不用进行从大到小的处理
代码实现:
#include algorithm
#includeiostream
using namespace std;
int n, m;
const int N 1010;
int v[N], w[N];
int f[N];
int main()
{cinnm;for (int i 1; i n; i)cin v[i] w[i];for (int i 0; i m; i)f[i] 0;//一件物品都没选 0-m的容积下价值都为0for(int i1;in;i){for(int jv[i];jm;j){f[j]max(f[j],f[j-v[i]]w[i]);//表示已经选入第i层 }}coutf[m];
} 完结撒花 本篇博客的内容【动态规划 :背包问题01背包完全背包】已经结束。 若对你有些许帮助可以点赞、关注、评论支持下博主你的支持将是我前进路上最大的动力。 若以上内容有任何问题欢迎在评论区指出。若对以上内容有任何不解都可私信评论询问。 诸君山顶见
