Zombie’s Treasure Chest

題目鏈接

https://cn.vjudge.net/problem/UVA-12325

題意

兩種物品無窮多個(gè),第一種物品重量$s_1$,價(jià)值$v_1$,第二種物品重量$s_2$,價(jià)值$v_2$,背包重$n$,求能裝的最大價(jià)值之和. 數(shù)據(jù)全都是$2e9$.也就是兩種物品的完全背包.

題解

不可思議吧,這題還能模擬退火?

但仔細(xì)一想,求解最優(yōu)值,而且隨機(jī)解的生成也很簡單,當(dāng)然可以嗎,模擬退火搞啦.

模擬退火的板子可以到我以前的博客里找到,現(xiàn)在默認(rèn)大家都知道模擬退火怎么寫了.

這道題我雖然用模擬退火$A$掉了,但也嘗試了好多發(fā),現(xiàn)在把我采坑的過程根大家分享一下.

嘗試一

直接套板子,設(shè)$x$為第一種物品取的個(gè)數(shù),顯然$x\in [0,?\frac{n}{s_1}?]$,那么第二種物品的個(gè)數(shù)就是$y=?\frac{n?s_1?v_1}{s_2}?$.

因此模擬退火的時(shí)候我可以在區(qū)間$[0,?\frac{n}{s_1}?]$中隨機(jī)一個(gè)數(shù)作為$x$,然后計(jì)算$y$,并且計(jì)算能量值$E=x?v_1+y?v_2$.

最后調(diào)調(diào)參數(shù),使得平衡一下答案精度和時(shí)間復(fù)雜度.

嘗試結(jié)果

多次嘗試以后,一直WA,自己造了組極端數(shù)據(jù)$2000000000,2,3,1,1$,發(fā)現(xiàn)根本過不去,總結(jié)原因:當(dāng)隨機(jī)區(qū)間過大的時(shí)候,很難隨機(jī)到正確解,所以算法就在某個(gè)半山腰停住了.

嘗試二

要想能想要枚舉到最優(yōu)解,區(qū)間一定不能太大.我們可以分塊進(jìn)行模擬退火,這樣可以保證每次隨機(jī)的區(qū)間不會太大,區(qū)間上的某一個(gè)點(diǎn)被隨機(jī)到的概率就更大了,這種做法我還沒有試過,但是感覺應(yīng)該可行.我們進(jìn)一步發(fā)現(xiàn),這個(gè)函數(shù)的峰不會太多(實(shí)際沒幾個(gè))大致是具有單調(diào)性質(zhì)的,因此我們采用二分區(qū)間的做法,即對于當(dāng)前區(qū)間,用模擬退火算出一個(gè)最優(yōu)解,然后用這個(gè)解與區(qū)間中點(diǎn)做比較從而確定下一個(gè)需要進(jìn)行模擬退火的區(qū)間.

通過多次調(diào)參之后:

代碼

#include <iostream> #include <algorithm> #include <cmath> #include <ctime> #include <cstring> int T,cas; long long n,s1,v1,s2,v2; double randfloat() {return rand()/(RAND_MAX+0.0); } void solve() {std::cin >> n >> s1 >> v1 >> s2 >> v2;long long ansE = 0,ansx = 0;long long nowE = 0,x = 0;long long low = 0,up = n/s1;for(int cc = 1;cc <= 20;++cc) {double T0 = 1000000,Tk = 1,T = T0,d = 0.999;while(T > Tk) {long long newx = low + rand()%(up-low+1);long long newE = newx * v1 + ((n-newx*s1)/s2)*v2;if(newE < nowE || randfloat() > exp((nowE-newE)/T)) {nowE = newE;x = newx;}T *= d;if(newE > ansE) {ansE = newE;ansx = newx;}}long long mid = (low + up)/2;if(ansx > mid) low = mid;else up = mid;}std::cout << "Case #" << ++cas << ": " << ansE << std::endl; } int main() {std::ios::sync_with_stdio(false);std::cin >> T;while(T--) solve();return 0; }

總結(jié)

以上是生活随笔為你收集整理的Uva12325 Zombie's Treasure Chest [二分区间+模拟退火]的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

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