【练习-9】Zombie’s Treasure Chest

题目大意：

一些勇敢的战士来到一个失落的村庄。他们非常幸运，发现了很多宝藏和一个大宝箱，但也发现了愤怒的僵尸。
战士们非常勇敢，他们决定打败僵尸，然后把所有的宝藏都带回来。一场旷日持久的残酷战斗从早到晚持续着，战士们发现僵尸是不死的，不可战胜的。
当然，宝藏不应该留在这里。不幸的是，由于宝箱容量的限制，战士们无法用宝箱携带所有的宝藏。事实上，珍宝只有两种：祖母绿和蓝宝石。所有的祖母绿在大小和价值上都是相等的，而且数量是无限的。蓝宝石也是。
身为拥有魔法神器的战士们的牧师：电脑，考虑到箱子的大小，每种宝石的价值和大小，你应该计算出我们战士们能带回的宝藏的最大价值。

AC代码：

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 1e5+5;
const ll mod = 1e9+7;
struct node{
    
	ll s,v;
};
node mx,mn,a[2];
int main()
{
    
	int t,V;
	cin>>t;
	for(int i=1;i<=t;i++)
	{
    
		cin>>V>>a[0].s>>a[0].v>>a[1].s>>a[1].v;
		ll t1 = a[0].v*a[1].s;
		ll t2 = a[1].v*a[0].s;
		ll res = 0;
		if(t1>=t2)
			mx.s=a[0].s,mx.v=a[0].v,mn.s=a[1].s,mn.v=a[1].v;
		else
			mx.s=a[1].s,mx.v=a[1].v,mn.s=a[0].s,mn.v=a[0].v;
		ll top = V/mn.s;
		top = min(top,mx.s-1);
		for(ll j=0;j<=top;j++)
		{
    
			ll tmp1=j*mn.v;
			ll tmp2=(V-j*mn.s)/mx.s*mx.v;
			res = max(res,tmp1+tmp2);
		}		
		printf("Case #%d: %lld\n",i,res);
	}
    return 0;
}

这道题简化的是取低价值物品数量的范围。
首先，我们知道：
箱子的体积是V
每个物品1 的体积是 s1,价值是 v1。
每个物品2 的体积是 s2 ,价值是v2。
那么当有s2个物品1时，物品1的体积是s2 * s1，价值是 s2 * v1.
同理当有s1个物品2时，物品2的体积是s1 * s2，价值是 s1 * v2.

很显然这时 ：物品1的体积 = 物品2的体积，而 物品1 的价值 不一定等于 物品2的价值。
我们假设相同体积下物品1的价值更高：
也就是说体积相同时，s2 * v1 > s1 * v2.
反过来说，当有s1个物品2时他的价值必然低于 s2个物品1，那么物品2的数量肯定是小于s1的。
也就是说，物品1尽可能的取，而物品2最多取s1-1个。

当然这不是最简化的，明显取最小公倍数lcm时物品2取得个数会更少（时间复杂度更低）。