牛客题霸 -- 【模板】完全背包

2023-10-03 16:30
文章标签 模板 背包 客题 完全

本文主要是介绍牛客题霸 -- 【模板】完全背包,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

参考代码:

未优化的代码:

int n;
int V;
const int N=1010;
int v[N];
int w[N];
int dp[N][N];int main()
{cin>>n>>V;for(int i=1;i<=n;i++){cin>>v[i]>>w[i];}//第一问://dp表中的第一行全是0,无需初始化//dp表第一列在填写dp表的时候再填//填表for(int i=1;i<=n;i++){for(int j=0;j<=V;j++){//状态转移方程dp[i][j]=dp[i-1][j];if(j>=v[i]){dp[i][j]=max(dp[i][j],dp[i][j-v[i]]+w[i]);}}}//输出结果cout<<dp[n][V]<<endl;//清空dp表memset(dp,0,sizeof(dp));//第二问://初始化第一行dp[0][0]=0;for(int j=1;j<=V;j++){dp[0][j]=-1;}//第一列无需初始化,在填dp表的时候再填写//填表for(int i=1;i<=n;i++){for(int j=0;j<=V;j++){//状态转移方程dp[i][j]=dp[i-1][j];if(j>=v[i]&&dp[i][j-v[i]]!=-1){dp[i][j]=max(dp[i][j],dp[i][j-v[i]]+w[i]);}}}cout<<(dp[n][V]==-1?0:dp[n][V])<<endl;return 0;
}

优化后的代码:


int n;
int V;
const int N=1010;
int v[N];
int w[N];
int dp[N];int main()
{cin>>n>>V;for(int i=1;i<=n;i++){cin>>v[i]>>w[i];}//第一问://dp表中的第一行全是0,无需初始化//填表for(int i=1;i<=n;i++){//一定要从左往右遍历,具体原因看图解for(int j=v[i];j<=V;j++){//状态转移方程dp[j]=max(dp[j],dp[j-v[i]]+w[i]);}}//输出结果cout<<dp[V]<<endl;//清空dp表memset(dp,0,sizeof(dp));//第二问://初始化第一行dp[0]=0;for(int j=1;j<=V;j++){dp[j]=-1;}//填表for(int i=1;i<=n;i++){//一定要从左往右遍历,具体原因看图解for(int j=v[i];j<=V;j++){//状态转移方程if(dp[j-v[i]]!=-1){dp[j]=max(dp[j],dp[j-v[i]]+w[i]);}}}cout<<(dp[V]==-1?0:dp[V])<<endl;return 0;
}

你学会了吗???

这篇关于牛客题霸 -- 【模板】完全背包的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/623

相关文章

C++中函数模板与类模板的简单使用及区别介绍

《C++中函数模板与类模板的简单使用及区别介绍》这篇文章介绍了C++中的模板机制,包括函数模板和类模板的概念、语法和实际应用,函数模板通过类型参数实现泛型操作,而类模板允许创建可处理多种数据类型的类,... 目录一、函数模板定义语法真实示例二、类模板三、关键区别四、注意事项 ‌在C++中,模板是实现泛型编程

Linux find 命令完全指南及核心用法

《Linuxfind命令完全指南及核心用法》find是Linux系统最强大的文件搜索工具,支持嵌套遍历、条件筛选、执行动作,下面给大家介绍Linuxfind命令完全指南,感兴趣的朋友一起看看吧... 目录一、基础搜索模式1. 按文件名搜索(精确/模糊匹配)2. 排除指定目录/文件二、根据文件类型筛选三、时间

JavaScript中的Map用法完全指南

《JavaScript中的Map用法完全指南》:本文主要介绍JavaScript中Map用法的相关资料,通过实例讲解了Map的创建、常用方法和迭代方式,还探讨了Map与对象的区别,并通过一个例子展... 目录引言1. 创建 Map2. Map 和对象的对比3. Map 的常用方法3.1 set(key, v

基于Java实现模板填充Word

《基于Java实现模板填充Word》这篇文章主要为大家详细介绍了如何用Java实现按产品经理提供的Word模板填充数据,并以word或pdf形式导出,有需要的小伙伴可以参考一下... Java实现按模板填充wor编程d本文讲解的需求是:我们需要把数据库中的某些数据按照 产品经理提供的 word模板,把数据

poj2576(二维背包)

题意:n个人分成两组,两组人数只差小于1 , 并且体重只差最小 对于人数要求恰好装满,对于体重要求尽量多,一开始没做出来,看了下解题,按照自己的感觉写,然后a了 状态转移方程:dp[i][j] = max(dp[i][j],dp[i-1][j-c[k]]+c[k]);其中i表示人数,j表示背包容量,k表示输入的体重的 代码如下: #include<iostream>#include<

hdu2159(二维背包)

这是我的第一道二维背包题,没想到自己一下子就A了,但是代码写的比较乱,下面的代码是我有重新修改的 状态转移:dp[i][j] = max(dp[i][j], dp[i-1][j-c[z]]+v[z]); 其中dp[i][j]表示,打了i个怪物,消耗j的耐力值,所得到的最大经验值 代码如下: #include<iostream>#include<algorithm>#include<

csu(背包的变形题)

题目链接 这是一道背包的变形题目。好题呀 题意:给n个怪物,m个人,每个人的魔法消耗和魔法伤害不同,求打死所有怪物所需的魔法 #include<iostream>#include<algorithm>#include<cstring>#include<stack>#include<queue>#include<set>//#include<u>#include<map

hdu1011(背包树形DP)

没有完全理解这题, m个人,攻打一个map,map的入口是1,在攻打某个结点之前要先攻打其他一个结点 dp[i][j]表示m个人攻打以第i个结点为根节点的子树得到的最优解 状态转移dp[i][ j ] = max(dp[i][j], dp[i][k]+dp[t][j-k]),其中t是i结点的子节点 代码如下: #include<iostream>#include<algorithm

poj3468(线段树成段更新模板题)

题意:包括两个操作:1、将[a.b]上的数字加上v;2、查询区间[a,b]上的和 下面的介绍是下解题思路: 首先介绍  lazy-tag思想:用一个变量记录每一个线段树节点的变化值,当这部分线段的一致性被破坏我们就将这个变化值传递给子区间,大大增加了线段树的效率。 比如现在需要对[a,b]区间值进行加c操作,那么就从根节点[1,n]开始调用update函数进行操作,如果刚好执行到一个子节点,

hdu1171(母函数或多重背包)

题意:把物品分成两份,使得价值最接近 可以用背包,或者是母函数来解,母函数(1 + x^v+x^2v+.....+x^num*v)(1 + x^v+x^2v+.....+x^num*v)(1 + x^v+x^2v+.....+x^num*v) 其中指数为价值,每一项的数目为(该物品数+1)个 代码如下: #include<iostream>#include<algorithm>