做catalog的免费网站,中国铁路建设行业协会网站,免费seo网站自动推广,烟台网站建设 烟台网亿网络公司Halo#xff0c;这里是Ppeua。平时主要更新C语言#xff0c;C#xff0c;数据结构算法......感兴趣就关注我吧#xff01;你定不会失望。 #x1f308;个人主页#xff1a;主页链接 #x1f308;算法专栏#xff1a;专栏链接 我会一直往里填充内容哒#xff01; … Halo这里是Ppeua。平时主要更新C语言C数据结构算法......感兴趣就关注我吧你定不会失望。 个人主页主页链接 算法专栏专栏链接 我会一直往里填充内容哒 LeetCode专栏专栏链接 目前在刷初级算法的LeetBook 。若每日一题当中有力所能及的题目也会当天做完发出 代码仓库Gitee链接 点击关注收获更多优质内容 目录
题目:多重背包问题
题解:
代码实现: 优化
代码实现:
题目:分组背包问题 题解
代码实现:
完结撒花 题目:多重背包问题 题解:
与完全背包问题不同的是每种东西都是有限件前两种状态就不再过多赘述有疑问的uu们可以去看看这篇文章完全背包第三种状态我们直接枚举即可当能拿下k个物品时与不拿k件物品去最大值。
代码实现:
#includeiostream
#includealgorithm
using namespace std;
const int N1100;
int v[N],s[N],w[N],f[N][N];int main()
{int n0,V0;cinnV;for(int i1;in;i){cinv[i]w[i]s[i];}for(int i1;in;i){for(int j1;jV;j){for(int k0;k*v[i]jks[i];k)f[i][j]max(f[i][j],f[i-1][j-k*v[i]]w[i]*k);}}coutf[n][V];
}优化
这种做法虽然简单易懂但时间复杂度为n^3很容易就TLE了所以我们必须优化一下。
这里有利用了一下快速幂背增的思想不知道的uu们听我细说
任何一个正整数都可以由二进制来表示废话那么我们要取得价值是不是也可以由二进制表示呢
例如 我们有 1 2 4价值得东西那我们就可以由这三个东西凑出0~7之间任何一个数
由3个物品的表示凑出了7个情况效率就高了
假设我们要凑0~9的任何一个数呢那么1 2 4就无法表示了我们可以给这区间加上一个2是不是就可以表示0~9之间的任何一个情况了呢。
换到这题来看数量为s的物品可以拆分为log s 个东西就可以枚举出s个物品的情况对应的价值乘上倍数k即可满足上面所说情况所以对应的问题就变成了01背包问题
代码实现:
#includeiostream
#includealgorithm
using namespace std;
const int N110000000;
int v[N],s[N],w[N],f[N][N];int solution2()
{int n0,V0;cinnV;int cnt0;int k1;for(int i1;in;i){int a0,b0,s0;cinabs;int k1;while(ks){v[cnt]a*k;w[cnt]b*k; s-k;k*2;}if(s0){v[cnt]s*a;w[cnt]s*b;}}ncnt;for(int i1;in;i){for(int jV;jv[i];j--)f[j]max(f[j],f[j-v[i]]w[i]);}coutf[V];
}
题目:分组背包问题 题解
这题与完全背包问题也十分的相似就是将一件物品无限拿变成了一组物品挑一个。
代码实现:
#includeiostream
#includealgorithm
using namespace std;
const int N110;
int v[N][N],w[N][N],s[N],f[N];
int main()
{int n0,m0;cinnm;for(int i1;in;i){cins[i];for(int j0;js[i];j){cinv[i][j];cinw[i][j];}}for(int i1;in;i){for(int jm;j0;j--){for(int k0;ks[i];k){if(jv[i][k])f[j]max(f[j],f[j-v[i][k]]w[i][k]);}}}coutf[m];
}
完结撒花 本篇博客的内容【动态规划多重背包问题分组背包问题】已经结束。 若对你有些许帮助可以点赞、关注、评论支持下博主你的支持将是我前进路上最大的动力。 若以上内容有任何问题欢迎在评论区指出。若对以上内容有任何不解都可私信评论询问。 诸君山顶见
