，通常可以用最优性剪枝。比如在求迷宫最短路的时候，如果发现当前的步数已经超过了当前最优解，那从当前状态开始的搜索都是多余的，因为这样搜索下去永远都搜不到更优的解。通过这样的剪枝，可以省去大量冗余的计算。
【例3】The Robbery （POJ 3900）。
Description
In the downtown of Bucharest there is a very big bank with a very big vault. Inside the vault there are N very big boxes numbered from 1 to N. Inside the box with number k there are k very big diamonds, each of weight Wk and cost Ck.
John and Brus are inside the vault at the moment. They would like to steal everything, but unfortunately they are able to carry diamonds with the total weight not exceeding M.
Your task is to help John and Brus to choose diamonds with the total weight less than or
equal to M and the maximal possible total cost.
Input
The first line contains single integer T – the number of test cases. Each test case starts with a line containing two integers N and M separated by a single space. The next line contains N integers Wk separated by single spaces. The following line contains N integers Ck separated by single spaces.
Output
For each test case print a single line containing the maximal possible total cost of diamonds.
Sample Input
2
2 4
3 2
5 3
3 100
4 7 1
5 9 2
Sample Output
6
29
Hint
Constraints:
1 ≤ T ≤ 74,
1 ≤ N ≤ 15,
1 ≤ M ≤ 1000000000 (10
9),
1 ≤ Wk, Ck ≤ 1000000000 (10
9).
（1）编程思路。
利用贪心的思想先对箱子进行排序，关键字为性价比（Ck/Wk）。也就是单位重量的价值最高的排第一。搜索的时候采用的剪枝策略有：
剪枝1：之后所有的钻石价值+目前已经得到的价值<=ans，则剪枝。
剪枝2：剩下的重量全部装目前最高性价比的钻石+目前已经得到的价值<=ans，则剪枝。
（2）源程序。
#include <iostream>
#include<algorithm>
using namespace std;
typedef __int64 ll;
int m,n;
ll ans;
bool flag;
struct node
{
ll w,c;
int num;
}lcm[20];
ll bsum[20];
int cmp(struct node a,struct node b)
{
return a.c * b.w > b.c * a.w; // 按性价比降序排列
}
void dfs(int cur,ll sum,int remain)
// cur搜到的当前位置，sum当前的总价值,remain当前还剩多少重量
{
if(remain < 0) return;
if(flag) return;
if(cur == n)
{
if(ans < sum)
ans = sum;
return;
}
if(sum + bsum[cur] <= ans) return; // 剪枝1
if(sum + remain*(lcm[cur].c*1.0/lcm[cur].w) <= ans) // 剪枝2
return;
if(remain == 0) // 因为先贪心了一下，所以第一次恰好凑成m的重量的一定是最优解
{
ans = sum;
flag = true;
return;
}
for(int i = lcm[cur].num;i >= 0;i --)
{
if (remain >= i * lcm[cur].w)
dfs(cur + 1,sum + i * lcm[cur].c,remain - i * lcm[cur].w);