首页 > 代码库 > uva 12325 宝箱
uva 12325 宝箱
题目链接：https://uva.onlinejudge.org/external/123/12325.pdf
一开始是完全背包，那个容量是一个32位数字，存不下。
然后暴力枚举，当n很大，s1,s2很小的时候，是不行的。
然后一个一个枚举，竟然还是超时。
其实，当一个一个枚举的时候，可以这样想，当我的某一种比较小的时候就可以枚举他。
但是要是s1,s2都很小的时候，枚举哪个都是超时的。
这个时候，可以这样考虑，假设两中体积相等（1宝贝s2个，2宝贝s1个），但是他有一个性价比，价值分别是s2*v1 和 s1*v2;
那么如果1宝贝价值大一点，那么2宝贝肯定个数小于s1个，枚举这s1个就OK了
1 /* 2 #include <cstdio> 3 #include <cstring> 4 #include <algorithm> 5 #include <iostream> 6 7 using namespace std; 8 9 int d[10000000];10 int s1,v1,s2,v2;11 12 int dp(int s) {13 int& ans = d[s];14 if(ans>=0) return ans;15 ans = 0;16 if(s-s1>=0)ans = max(ans,dp(s-s1)+v1);17 if(s-s2>=0)ans = max(ans,dp(s-s2)+v2);18 return ans;19 }20 21 22 int main()23 {24 int t;25 cin>>t;26 int kase = 1;27 while(t--) {28 memset(d,-1,sizeof(d));29 int s;30 cin>>s;31 cin>>s1>>v1>>s2>>v2;32 int ans = dp(s);33 printf("Case #%d: %d\n",kase++,ans);34 }35 return 0;36 }37 */38 39 40 #include <cstdio>41 #include <cstring>42 #include <algorithm>43 #include <iostream>44 45 using namespace std;46 47 #define INF 500048 49 int main()50 {51 52 int t;53 cin>>t;54 long long s,s1,v1,s2,v2;55 int kase= 1;56 while(t--)57 {58 long long ans = 0;59 cin>>s>>s1>>v1>>s2>>v2;60 61 if(s/s1<INF)62 {63 for(int i=0; i*s1<=s; i++)64 {65 ans = max(ans,(s-i*s1)/s2*v2+i*v1);66 }67 }68 else if(s/s2<INF)69 {70 for(int i=0; i*s2<=s; i++)71 {72 ans = max(ans,(s-i*s2)/s1*v1+i*v2);73 }74 }75 else {76 long long sum1 = s2*v1;77 long long sum2 = s1*v2;78 if(sum1>sum2) { //1 de xing jia bi gao79 for(long long i=0;i<s1;i++)80 {81 long long temp = s - i*s2;82 ans = max(ans,temp/s1*v1+i*v2);83 84 }85 86 }87 else {88 for(long long i=0;i<s2;i++) {89 long long temp = s - i*s1;90 ans = max(ans,temp/s2*v2+i*v1);91 }92 }93 }94 printf("Case #%d: %lld\n",kase++,ans);95 }96 return 0;97 }
uva 12325 宝箱
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。