題意：給定兩個箱子體積s1,s2，價值v1,v2，給出一個體積為V的寶箱，求可裝入的最大價值。

分析：正常寫肯定是超時的，把狀況簡化，第一種，當(dāng)s1,s2都很小時，就看它們的價值比，v1/s1 ，v2/s2當(dāng)v1/s1>v2/s2時，就說明v1的價值更大，更多的搜索v1，v2寶箱最多搜索s1個。下面同理。

第二種，當(dāng)s1，s2都很大，s1>s2時，優(yōu)先搜索s1，s1很快就能搜索完。

代碼部分：

#include<cstdio> #include<cstring> #include<cctype> #include<queue> #include<iostream> #include<vector> #include<list> using namespace std; typedef long long LL; int s1, s2, v1, v2,M; int main() {int n;cin >> n;for (int i = 1; i <= n; i++) {cin>>M >> s1 >> v1 >> s2 >> v2;LL curM = 0;if (s1 < s2) {int temp = s1;s1 = s2;s2 = temp;temp = v1;v1 = v2;v2 = temp;}if (M/s1>=65536) {for (LL j = 0; j <= s1; j++) {curM = max(curM, j*v2 + ((M - j * s2) / s1)*v1);}for (LL j = 0; j <= s2; j++) {curM = max(curM, j*v1 + ((M - j * s1) / s2)*v2);}}else {for (LL j = 0; s1*j<=M; j++) {curM = max(curM, j*v1 + ((M - j * s1) / s2)*v2);}}cout << "Case #" << i <<": "<<curM<< endl;}//system("pause");return 0; }

?

總結(jié)

以上是生活随笔為你收集整理的UVA12325Zombie's Treasure Chest 宝箱的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。