C. Come to a spring outing
Time Limit: 1000ms
Case Time Limit: 1000ms
Memory Limit: 65536KB
64-bit integer IO format: %lld Java class name: Main
Submit Status PID: 29358
Font Size: + -
Spring is coming，WHU ACM team plans to organize a spring outing because of the good weather. They bought a lot of things to eat and use (collectively referred to the item), each item has a volume. In order to take them away, they also bought 3 backpacks, each backpack can be fitted to a certain volume of things, and the question is there: Can they take all the items away?
Input
Input contains several test cases. The first line is an integer T indicates the number of test cases. For each test case, the first line is two integer n and m(1<=n<=30,1<=m<=400), indicate the number of items and the capacity of each backpack. The second line contains n integers, the i-th integer wi(1<=wi<=400) shows the volume of the i-th item.
Output
For each set of data, output the case number first, and then output a string, “Yes” means they can take all things away, and “No” means they cannot take all things away by three backpack.
Sample Input
2 4 3 1 2 3 3 4 3 2 2 2 2
Sample Output
Case 1: Yes Case 2: No
Submit Status PID: 29358
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
int w[33];
int n,v;
bool cmp(int a,int b)
{
return a>b;
}
bool OK=false;
void dfs(int i,int v1,int v2,int v3)
{
if(i==n){ OK=true; return; }
if(OK==true) return;
if(v1+w <=v)
dfs(i+1,v1+w ,v2,v3);
if(v2+w <=v)
dfs(i+1,v1,v2+w ,v3);
if(v3+w <=v)
dfs(i+1,v1,v2,v3+w );
}
int main()
{
int T;
cin>>T;
int cas=0;
while(T--)
{
int sum=0;
cin>>n>>v;
for(int i=0;i<n;i++)
{
cin>>w ; sum+=w;
}
if(sum>3*v)
{
printf("Case %d: No\n",++cas);
continue;
}
OK=false;
sort(w,w+n,cmp);
dfs(0,0,0,0);
if(OK)
printf("Case %d: Yes\n",++cas);
else
printf("Case %d: No\n",++cas);
}
return 0;
}