电脑iis做网站,wordpress改插件难吗,创新营销方式有哪些,高校学生红色网站建设Zombie’s Treasure Chest
题目链接
https://cn.vjudge.net/problem/UVA-12325
题意
两种物品无穷多个,第一种物品重量s1s_1s1,价值v1v_1v1,第二种物品重量s2s_2s2,价值v2v_2v2,背包重nnn,求能装的最大价值之和. 数据全都是2e92e92e9.也就是两种物品的完全背包.
题…Zombie’s Treasure Chest
题目链接
https://cn.vjudge.net/problem/UVA-12325
题意
两种物品无穷多个,第一种物品重量s1s_1s1,价值v1v_1v1,第二种物品重量s2s_2s2,价值v2v_2v2,背包重nnn,求能装的最大价值之和. 数据全都是2e92e92e9.也就是两种物品的完全背包.
题解
不可思议吧,这题还能模拟退火?
但仔细一想,求解最优值,而且随机解的生成也很简单,当然可以吗,模拟退火搞啦.
模拟退火的板子可以到我以前的博客里找到,现在默认大家都知道模拟退火怎么写了.
这道题我虽然用模拟退火AAA掉了,但也尝试了好多发,现在把我采坑的过程根大家分享一下.
尝试一
直接套板子,设xxx为第一种物品取的个数,显然x∈[0,⌊ns1⌋]x \in [0,\lfloor \frac{n}{s_1} \rfloor]x∈[0,⌊s1n⌋],那么第二种物品的个数就是y⌊n−s1∗v1s2⌋y \lfloor \frac{n-s_1*v_1}{s_2} \rfloory⌊s2n−s1∗v1⌋.
因此模拟退火的时候我可以在区间[0,⌊ns1⌋][0,\lfloor \frac{n}{s_1} \rfloor][0,⌊s1n⌋]中随机一个数作为xxx,然后计算yyy,并且计算能量值Ex∗v1y∗v2E x*v_1y*v_2Ex∗v1y∗v2.
最后调调参数,使得平衡一下答案精度和时间复杂度.
尝试结果
多次尝试以后,一直WA,自己造了组极端数据2000000000,2,3,1,12000000000,2,3,1,12000000000,2,3,1,1,发现根本过不去,总结原因:当随机区间过大的时候,很难随机到正确解,所以算法就在某个半山腰停住了.
尝试二
要想能想要枚举到最优解,区间一定不能太大.我们可以分块进行模拟退火,这样可以保证每次随机的区间不会太大,区间上的某一个点被随机到的概率就更大了,这种做法我还没有试过,但是感觉应该可行.我们进一步发现,这个函数的峰不会太多(实际没几个)大致是具有单调性质的,因此我们采用二分区间的做法,即对于当前区间,用模拟退火算出一个最优解,然后用这个解与区间中点做比较从而确定下一个需要进行模拟退火的区间.
通过多次调参之后:
代码
#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_MAX0.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-low1);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;
}
