生活随笔
收集整理的这篇文章主要介绍了
2020ICPC(小米邀请赛2) - Knapsack(贪心+dp)
小编觉得挺不错的,现在分享给大家,帮大家做个参考.
题目链接：点击查看
题目大意：给出 n 个物品，每个物品都有体积和价值，现在问容量为 m 的背包最多可以装下多少价值的物品
题目分析：本题正解应该是斜率优化dp，然鹅看了大佬们的博客讲解后，感觉不是自己可以触碰的领域，所以用了一种 “投机取巧” 的方法实现本题
直接进行 01 背包时间复杂度是 n * m 级别的，但是每个物品最大的容量是 100，所以考虑大范围贪心小范围 dp，贪心决策就是按照每个物品单位体积的价值降序排序，然后贪心取即可，小范围进行背包选择最优价值，阈值我设置的是 200，只要在规定的时间复杂度内，阈值可以适当增大
代码：
//#pragma GCC optimize(2)
//#pragma GCC optimize("Ofast","inline","-ffast-math")
//#pragma GCC target("avx,sse2,sse3,sse4,mmx")
#include<iostream>
#include<cstdio>
#include<string>
#include<ctime>
#include<cmath>
#include<cstring>
#include<algorithm>
#include<stack>
#include<climits>
#include<queue>
#include<map>
#include<set>
#include<sstream>
#include<cassert>
#include<bitset>
using namespace std;typedef long long LL;typedef unsigned long long ull;const int inf=0x3f3f3f3f;const int N=1e6+100;struct Node
{LL cost,val;void input(){scanf("%lld%lld",&cost,&val);}bool operator<(const Node& t)const{return val*t.cost>t.val*cost;}
}node[N];LL dp[210];int main()
{
#ifndef ONLINE_JUDGE
// freopen("data.in.txt","r",stdin);
// freopen("data.out.txt","w",stdout);
#endif
// ios::sync_with_stdio(false);int n,m;while(scanf("%d%d",&n,&m)!=EOF){memset(dp,0,sizeof(dp));for(int i=1;i<=n;i++)node[i].input();sort(node+1,node+1+n);LL ans=0;int st=1;while(st<=n&&m>=200){ans+=node[st].val;m-=node[st].cost;st++;}for(int i=st;i<=n;i++)for(int j=m;j>=node[i].cost;j--)dp[j]=max(dp[j],dp[j-node[i].cost]+node[i].val);printf("%lld\n",ans+dp[m]);}return 0;
}
总结
以上是生活随笔为你收集整理的2020ICPC(小米邀请赛2) - Knapsack(贪心+dp)的全部内容，希望文章能够帮你解决所遇到的问题。
如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。
