用邮箱地址做网站域名好吗,企业网站建设的特点,衡水网站建设选哪家,电脑做微信推送的网站引言
多重背包#xff0c;相对于01背包来说#xff0c;多重背包是每个物品会有相应的个数#xff0c;最多可以选那么多个#xff0c;因而对于朴素多重背包#xff0c;需要在01背包的基础上#xff0c;再加一层物品的循环
朴素多重背包例题
P2347 [NOIP1996 提高组] 砝…引言
多重背包相对于01背包来说多重背包是每个物品会有相应的个数最多可以选那么多个因而对于朴素多重背包需要在01背包的基础上再加一层物品的循环
朴素多重背包例题
P2347 [NOIP1996 提高组] 砝码称重 题意就是说有六种砝码每种砝码有自己的个数问你能达到的重量搭配是多少
题解标准的多重背包我们可以用dp[ j ]去表示 j 重量能否达到如果能达到就是1如果不能打达到就是0最后遍历一遍dp数组去判断有多少个1即可
#includebits/stdc.h
using namespace std;
int a[7];
int w[7]{0,1,2,3,5,10,20};
int dp[1050];int main()
{for(int i1;i6;i)cina[i];dp[0]1;for(int i1;i6;i){for(int j1050;j0;j--){for(int k0;ka[i];k)//遍历第i个物品选的个数{if(dp[j]1){dp[jk*w[i]]1;}}}}int sum0;for(int i1;i1000;i)if(dp[i]!0)sum;coutTotalsum;return 0;
} P6771 [USACO05MAR] Space Elevator 太空电梯 题意就是说给你n中方块每个方块有自己的高度和最大搭建的限制在某个高度以后不能用这种方块,还有方块的数量
思路这是一个变式我们需要将其组装成一个结构体然后对a数组进行排序从小到大进行排序然后进行多重背包即可
#includebits/stdc.h
using namespace std;
int n;
struct node{int h;int limit;int num;
}a[405];
int dp[40005];//能否达到高度为j能达到为1不能为0bool cmp(node a,node b)
{return a.limitb.limit;
}int main()
{cinn;for(int i1;in;i)cina[i].ha[i].limita[i].num;dp[0]1;sort(a1,a1n,cmp);for(int i1;in;i){for(int ja[i].limit;j0;j--){for(int k0;ka[i].numjk*a[i].ha[i].limit;k){if(dp[j]1){dp[jk*a[i].h]1;}}}}for(int ia[n].limit;i0;i--){if(dp[i]1){couti;return 0;}}return 0;
} P5365 [SNOI2017] 英雄联盟 题意有n个英雄每个英雄有k个皮肤对于一个英雄的所有皮肤都是一个价格c,但是我又想要m中搭配正常的求法是算出m个搭配至少要多少钱但是这题m的数据太大了只能通过对于一定的钱其搭配数是多少
思路dp数组表示的是对于j元总共有多少的搭配数然后判断这个搭配数是否大于m从前向后遍历找到第一个大于m种搭配的位置那个下标就是最小花费
//英雄联盟
//这题皮肤搭配数量太大了肯定不能当数组要换成j个q币能搞得最大皮肤搭配
#includebits/stdc.h
using namespace std;
#define int long long
int n,m;
int num[135];
int w[135];
int dp[270005];
signed main()
{cinnm;int sum0;//计算总金额 for(int i1;in;i){cinnum[i];}for(int i1;in;i){cinw[i];sumnum[i]*w[i];}dp[0]1;for(int i1;in;i){for(int jsum;j0;j--){for(int k0;knum[i]k*w[i]j;k){dp[j]max(dp[j],dp[j-k*w[i]]*k);}}}for(int i1;isum;i){if(dp[i]m){couti;return 0;}}return 0;
}
二进制优化
用到的是二进制拆分思想
比如说对于50这个数我们用二进制拆分可以分为 1,2,4,8,16,19这五个数我们这五个数搭配可以组成50以内的所有自然数所以我们二进制优化也是通过拆分每个物品的个数从而降低时间复杂度从而形成完全的01背包问题
二进制优化例题
P1776 宝物筛选 一看这道题如果用正常的多重背包时间复杂度为100*40000*100000肯定会爆数据的所以我们要用二进制优化将时间复杂度变为4e6*log2(100000)这样就大大降低的时间的复杂度
将物品数量进行二进制拆分
#includebits/stdc.h
using namespace std;
#define int long long
int n,m;
int v[1405];
int w[1405];
int dp[40005];signed main()
{cinnm;int vv,ww,mm;int cnt0;for(int i1;in;i){cinvvwwmm;for(int j1;jmm;j1){cnt;v[cnt]j*vv;w[cnt]j*ww;mm-j;}if(mm){cnt;v[cnt]mm*vv;w[cnt]mm*ww;}}for(int i1;icnt;i){for(int jm;jw[i];j--){dp[j]max(dp[j],dp[j-w[i]]v[i]);}}coutdp[m];return 0;
}
