The Robbery

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 (109), 
1 ≤ Wk, Ck ≤ 1000000000 (109).
Source

Southeastern European Regional Programming Contest 2009

题目分析：

我和很多人一样，第一感觉这是一个多重背包的问题，结果不断爆内存和超时，

后来看了数据范围，才发现，应该用dfs来做，直接暴力裸搜显卡会超时，优化

和剪枝是必须的，下面介绍三个优化与剪枝：

1、将所有砖石按性价比从大到小排列

2、在搜索过程中，假设将还剩有的容量left全部全部装当前砖石，则可获得可能

      不存在的最大价值，如果这个价值小于ans，则可以退出该层搜索了

3、同样是在搜索过程中，假设将还剩有箱子的砖石的价值全部加上，如果这个价值

      小于ans，则也可以退出该层搜索了

# include<stdio.h>
# include<string.h>
long long  w[16],v[16],k[16];
int n,m,time;
long long ans,sum[16];
void swap(long long &x,long long &y)
{
    long long temp;
    temp=x; x=y; y=temp;
}
void sort()    //    优化一：按性价比从大到小排列
{
    long long i,j,temp;
    for (i=1;i<n;i++)
    for (j=i+1;j<=n;j++)
    if (v[i]*w[j]<v[j]*w[i])
    {
        swap(w[i],w[j]);
        swap(v[i],v[j]);
        swap(k[i],k[j]);
    }
}
void put(long long x)
{
    if (ans<x) ans=x;
}
void dfs(int left,int x,long long value)
{
    int i;
    if (x>n)
    {
        put(value);
        return;
    }
    if (time==30000000) return;
    double cost;
    cost=value+((double)left)/w[x]*v[x];
    if (cost<ans) return;           //优化二
    cost=value+sum[n]-sum[x-1];
    if (cost<ans) return;          //优化三
    for (i=k[x];i>=0;i--)
    if (left>=i*w[x])
    {
        time++;
        dfs(left-i*w[x],x+1,value+i*v[x]);
    }
}
int main()
{
    int i,t;
    long long weight;
    scanf("%d",&t);
    while (t--)
    {
        scanf("%d%d",&n,&m);
        weight=0;
        for (i=1;i<=n;i++)
        {
            scanf("%lld",&w[i]);
            weight+=w[i]*i;
        }
        for (i=1;i<=n;i++)
        {
            scanf("%lld",&v[i]);
            k[i]=i;
        }
        sort();
        sum[0]=0;
        for (i=1;i<=n;i++)
        {
            sum[i]=sum[i-1]+v[i]*k[i];
        }
        ans=0;
        int mm=m;
        for (i=1;i<=n;i++)
        if (mm>=w[i])
        {
            if (mm>=w[i]*k[i])
            {
                ans+=v[i]*k[i];
                mm-=w[i]*k[i];
            }
            else
            {
                ans+=(mm/w[i])*v[i];
                mm=mm-w[i]*(mm/w[i]);
            }
        }                     //首先构造一个可行的价值
        time=0;
        if (weight>m) dfs(m,1,0);
        else ans=sum[n];        //如果能全部装下，肯定直接输出所有价值之和啊
        printf("%lld\n",ans);
    }
}