首页 > 代码库 > 01背包(就地滚动)
01背包(就地滚动)
<span style="color:#3333ff;">/* __________________________________________________________________________________________________ * copyright: Grant Yuan * * algorithm: 01背包(就地滚动) * * time : 2014.7.18 * * declare : 题目中说N最大是3400多,但是一开始开了5000内存还是运行时错误,后来直接改了50000 * * * *_________________________________________________________________________________________________*</span>
<span style="color:#3333ff;"> I - 01背包(就地滚动) Time Limit:1000MS Memory Limit:65536KB 64bit IO Format:%I64d & %I64u Submit Status Description Bessie has gone to the mall's jewelry store and spies a charm bracelet. Of course, she'd like to fill it with the best charms possible from the N (1 ≤ N ≤ 3,402) available charms. Each charm i in the supplied list has a weight Wi (1 ≤ Wi ≤ 400), a 'desirability' factor Di (1 ≤ Di ≤ 100), and can be used at most once. Bessie can only support a charm bracelet whose weight is no more than M (1 ≤ M ≤ 12,880). Given that weight limit as a constraint and a list of the charms with their weights and desirability rating, deduce the maximum possible sum of ratings. Input * Line 1: Two space-separated integers: N and M * Lines 2..N+1: Line i+1 describes charm i with two space-separated integers: Wi and Di Output * Line 1: A single integer that is the greatest sum of charm desirabilities that can be achieved given the weight constraints Sample Input 4 6 1 4 2 6 3 12 2 7 Sample Output 23 */ #include<iostream> #include<cstdio> #include<cstdlib> #include<cstring> #include<algorithm> using namespace std; int w[50001]; int p[50001]; int sum; int n; int dp[50001]; int main() { cin>>n>>sum; for(int i=0;i<n;i++) cin>>w[i]>>p[i]; memset(dp,0,sizeof(dp)); for(int i=0;i<n;i++) for(int j=sum;j>=w[i];j--) { dp[j]=max(dp[j],dp[j-w[i]]+p[i]); } cout<<dp[sum]<<endl; return 0; } </span>
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。