大意：和背包的问题相似，第 i 个箱子有 i 颗钻石。钻石的重量，价值给出。然后再M的重量下背尽量多价值的钻石。
思路：直接暴搜然后剪枝。因为数据范围的原因无法用DP。
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <iostream>
using namespace std;
long long maxa(long long a,long long b)
{
return a>b?a:b;
} struct node
{
long long w;
long long v;
double vbw;
int id;
}Q[20]; int n,m;
long long ans;
long long sumv[20];
long long tot; bool cmp(node a,node b)
{
return a.vbw>b.vbw;
} void dfs(int pos,long long sum,int left)//分别是 搜到的当前位置 当前的总价值 当前还剩多少重量
{
ans=maxa(ans,sum);
if(pos>n)return; //越界 if(sum + sumv[pos-1] <=ans)return;//如果剩下的全背上都不比当前最优解好。就剪掉 if(sum + left * Q[pos].vbw <=ans)return; //在性价比排序的基础上，如果剩下的重量全部背这种性价比最高的还不能比最优解好。就剪掉 for(int k=Q[pos].id;k>=0;k--)
{
if(left - k*Q[pos].w <0)continue;
dfs(pos+1,sum+k*Q[pos].v,left-k*Q[pos].w);
}
} int main()
{
int T;
scanf("%d",&T);
while(T--)
{
ans=0;
scanf("%lld%lld",&n,&m);
tot=0;
for(int i=1;i<=n;i++)
{
scanf("%lld",&Q[i].w);
Q[i].id = i;
}
for(int i=1;i<=n;i++)
{
scanf("%lld",&Q[i].v);
tot+=i*Q[i].v;
} for(int i=1;i<=n;i++)
Q[i].vbw=1.0 * Q[i].v/Q[i].w; sort(Q+1,Q+n+1,cmp);
sumv[n]=0; for(int i=n;i>=1;i--)
{
//printf("i = %d Q[i].id = %d\n",i,Q[i].id);
sumv[i-1] = sumv[i] + Q[i].id*Q[i].v; //求出后缀和 不包括自身
}
/*for(int i=0;i<=n;i++)
printf("%lld ",sumv[i]);*/ dfs(1,0,m); printf("%lld\n",ans);
}
return 0;
}