首页 > 代码库 > FZU 2214 Knapsack problem (01背包)
FZU 2214 Knapsack problem (01背包)
题意:给你n种物品,每种只有一个,第i种物品的价值为Vi,重量为Wi,把这些物品放入一个重量限制为B的背包中,使得背包内的物品在重量不超过B的前提下,价值尽量大,输出最大价值
1 <= n <= 500
1 <= B, w[i] <= 1000000000
1 <= v[1]+v[2]+...+v[n] <= 5000
思路:我们从范围中可以看到这个物品的重量和背包所能承受的重量特别大,我们不能使用常规的01背包,我们可以把问题转化一下,我们定义d(i,j)是把第i个物品装入限制价值为j的背包中的最小重量,那么d(i,j)=min{d(i+1,j),d(i+1,j-v[i])+w[i]},然后为了减少内存开销我们可以把它转化为滚动数组的模式 d(j)=min{d(j),d(i-v)+w},最后只需要找到满足重量不大于B的最大价值就可以
代码:
#include <iostream> #include <cstdio> #include <cstring> #include <cmath> #include <algorithm> #define ll long long #define INF 0x3f3f3f3f using namespace std; int main(int argc, char const *argv[]) { int t; ll dp[5005]; ll n,B; cin>>t; while(t--) { scanf("%lld %lld",&n,&B); memset(dp,INF,sizeof(dp)); dp[0]=0; ll sum=0; for(int i=1;i<=n;i++) { ll v,w; scanf("%lld %lld",&w,&v); sum=sum+v; for(int j=sum;j>=v;j--) { dp[j]=min(dp[j],dp[j-v]+w); } } for(int j=sum;j>=0;j--) { if(dp[j]<=B) { cout<<j<<endl; break; } } } return 0; }
FZU 2214 Knapsack problem (01背包)
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。