织梦网站多少钱,生产厂家上什么网站做推广好,乐陵森林大队长李兵,免费刷赞网站推广免费背包型动态规划 一、背包 dp1. 01 背包#xff08;限量#xff09;2. 完全背包#xff08;不限量#xff09;3. 口诀 二、例题1. 和是质数的子集数2. 黄金的太阳3. 负数子集和4. NASA的⻝物计划 一、背包 dp
1. 01 背包#xff08;限量#xff09;
假如有这几个物品限量2. 完全背包不限量3. 口诀 二、例题1. 和是质数的子集数2. 黄金的太阳3. 负数子集和4. NASA的⻝物计划 一、背包 dp
1. 01 背包限量
假如有这几个物品前面的数是价值后面的数是体积52187146
则推导的 dp[][] 表格应该如下行表示宝石个数列表示背包容量变化
01234567800000000001005555555200555551853005555141819
总的来说可以用下面流程图简单概括
容量宝石体积装不进dp[i][j]dp[i-1][j]
容量宝石体积装或不装dp[i][j]max{dp[i-1][j],dp[i-1][j-w[i]]v[i]}模板
#includebits/stdc.h
using namespace std;
int n,m,w[10005],v[10005],dp[10005];
int main(){cinnm;for(int i1;in;i)cinw[i]v[i];for(int i1;in;i)for(int jm;jw[i];j--)dp[j]max(dp[j],v[i]dp[j-w[i]]);coutdp[m];return 0;
}2. 完全背包不限量
假如有这几个物品前面的数是价值后面的数是体积233445
则推导的 dp[][] 表格应该如下行表示宝石个数列表示背包容量变化
01234567800000000001000333666…
模板
#includebits/stdc.h
using namespace std;
int n,m,v[10005],e[10005],dp[10005];
int main(){cinnm;for(int i1;in;i)cinv[i]e[i];for(int i1;in;i)for(int jv[i];jm;j)dp[j]max(dp[j],e[i]dp[j-v[i]]);coutdp[m];return 0;
}
3. 口诀
遇到 dp 怎么办凉拌炒鸡蛋洛谷上面加颗蛋。翻个面金灿灿01 完全背模板。
二、例题
1. 和是质数的子集数
给出 n n n 个正整数问存在多少个子集使得子集中所有数的和是质数。
#includebits/stdc.h
using namespace std;
const int MAXN5e28;
const int MAXS1e58;
const int MOD1e97;
int n,s,a[MAXN],dp[MAXS];
bool isPrime(int n){if(n2)return 0;for(int i2;i*in;i)if(n%i0)return 0;return 1;
}
int main(){cinn;for(int i1;in;i)cina[i],sa[i];dp[0]1;for(int i1;in;i)for(int js;ja[i];j--)dp[j](dp[j]dp[j-a[i]])%MOD;int ans0;for(int i2;is;i)if(isPrime(i))ans(ansdp[i])%MOD;coutans;return 0;
}2. 黄金的太阳
黄金的太阳独创了一种精灵召唤技能。玩家在冒险中收集精灵然后就可以在战斗中利用精灵的能量使用各种召唤技能。 每种召唤技能需要消耗精灵的能量玩家的精灵能提供的总能量等于 m m m 点。当释放召唤技能时根据技能的消耗需要同等数量的能量消耗掉的能量不会再恢复。只要有足够的能量每种技能都可以无限次使用。 玩家目前收集的精灵能够提供的能量等于 m m m 点。有 n n n 种不同的召唤技能可以使用第 i i i 种技能的消耗为 c i c_i ci 点能量伤害为 d i d_i di。 敌人的体力为 H H H当总伤害大于等于 H H H 时敌人就被击败了。问击败敌人时还剩下的可以提供能量的精灵的最多数量。如果无法击败敌人输出 −1。
#includebits/stdc.h
using namespace std;
const int MAXN1e28;
const int MAXH1e58;
const int INF0x3f3f3f3f;
int n,m,h,c[MAXN],d[MAXN],dp[MAXH];
int main(){cinnmh;for(int i1;in;i)cinc[i]d[i];memset(dp,INF,sizeof(dp));dp[0]0;for(int i1;in;i)for(int j0;jh;j)dp[j]min(dp[j],dp[max(0,j-d[i])]c[i]);coutmax(-1,m-dp[h]);return 0;
}3. 负数子集和
#includebits/stdc.h
using namespace std;
const int MAXN5e18;
const int MAXS1e48;
const int MOD998244353;
int n,s;
mapint,intdp;//和为j的子集总数
int main(){cinns;dp[0]1;for(int i1,a;in;i){cina;if(a0)for(int jMAXS;j-MAXS;j--)dp[j](dp[j-a]dp[j])%MOD;elsefor(int j-MAXS;jMAXS;j)dp[j](dp[j-a]dp[j])%MOD;}coutdp[s]%MOD;return 0;
}4. NASA的⻝物计划
NASA美国航空航天局因为航天飞机的隔热瓦等其他安全技术问题一直大伤脑筋因此在各方压力下终止了航天飞机的历史但是此类事情会不会在以后发生谁也无法保证在遇到这类航天问题时解决方法也许只能让航天员出仓维修但是多次的维修会消耗航天员大量的能量因此NASA便想设计一种食品方案让体积和承重有限的条件下多装载一些高卡路里的食物. 航天飞机的体积有限当然如果载过重的物品燃料会浪费很多钱每件食品都有各自的体积、质量以及所含卡路里在告诉你体积和质量的最大值的情况下请输出能达到的食品方案所含卡路里的最大值当然每个食品只能使用一次.
#includebits/stdc.h
using namespace std;
const int MAXN5e28;
const int MAXV4e28;
const int MAXW4e28;
int n,vol,wt,v[MAXN],w[MAXN],c[MAXN],dp[MAXV][MAXW];
int main(){cinvolwtn;for(int i1;in;i)cinv[i]w[i]c[i];for(int i1;in;i)for(int jvol;jv[i];j--)//体积for(int kwt;kw[i];k--)//重量dp[j][k]max(dp[j][k],dp[j-v[i]][k-w[i]]c[i]);coutdp[vol][wt];return 0;
}
