A. Knapsack------------------------------------思维(贪心)

题意:
给定n个数和w,每个数都有一个权值ai. 问你如何选择使得权值之和在
[(w+1)/2,w] 之间。如果满足输出选择数的下标。如果不行输出-1

解析:
贪心，从大到小贪。

例:
n=6 w=12
1 1 1 1 1 11

如果从小到大贪，这个样例会输出-1.必须从大到小贪

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1e6+1000;
ll w;
struct node
{
	ll x;
	int pos;
 } a[N];
 int t,n;
 bool cmp(const node &a,const node &b)
 {
 	return a.x<b.x;
 }
int main()
{
	scanf("%d",&t);
	while(t--)
	{
		scanf("%d %lld",&n,&w);
		for(int i=1;i<=n;i++) scanf("%lld",&a[i].x),a[i].pos=i;
		sort(a+1,a+1+n,cmp);
		vector<int> v;
		ll sum=0;
		for(int i=1;i<=n;i++)
		{
			if(sum+a[i].x<=w)
			{
				sum+=a[i].x;
				v.push_back(a[i].pos);
			}
 		}
 		if(sum<(w+1)/2) puts("-1");
 		else{
 			

 		sort(v.begin(),v.end());
 		cout<<v.size()<<endl;
 		for(auto x:v){
 			cout<<x<<" ";
		 }
		 cout<<endl;
	}
	}
 }