(背包问题2)有N(O<N≤50)个物品，第i个物品体积为v[i](0≤v[i]≤10^18)，价值为w[i](0≤w[i]≤10^17)。现有一个容量为V(0≤V≤10^18)的背包。你需要选择一些物品使

得体积之和不超过V且价值最大。求出最大价值及方案。如有多种方案，尽可能选择编号较大的方案(即尽量选第n个，仍有多组解选第n-1个，以此类推)。

提示:将物品按标号是否大于n/2分成两组，每组内枚举如何选择。再在两组间确定方案。

试补全程序。

#include <iostream>


using namespace std;





const long long inf=___(1)___;


long long v[41];


long long w[41];


struct Item {


	long long value, weight, choose;


} itm[2][1<<20];





bool cmp1(Item a, Item b) {


	return a.value < b.value||(a.value == b.value && a.choose < b.choose);


}


bool cmp2(Item a, Item b) {


	return a.value < b.value||(a. value == b.value && a.choose==b.choose);


}


int get_id(int n) {


	for(int i=0; ; ++i)


		if(!(n>>i)) return i-1;


	}





void sort(Item item[], int L, int R) {


	if(L>= R) return;


	int x=rand()%(R-L+1)+L;


	swap(item[L], item[x]);


	int a=L+1,b= R;


	while (a<b) {


		while (a<b&& cmp1(item[a], item[L]))


			++a;


		while(a< b&& ___(2)___)


			--b;


		swap(item[a],item[b]);


	}


	while (b<= R&& item[b].value == item[L].value)


		++b;


	if (item[a].value < item[L].value)


		swap(item[a],item[L]);


		     sort(item, L, a-1);


		     sort(item, b, R);


	}





int solve(int L, int R, Item item[]) {





	item[0].value=0;


	item[0].choose = 0;


	int len = ___(3)___;


	for (int i=1; i <= len; ++i) {


		int tmp= ___(4)___;


		item[i].value = item[i - tmp].value + v[L + get_id(tmp)];


		item[i].weight = item[i - tmp].weight + w[L + get_id(tmp)];


		if (item[i].value > inf) item[i].value = inf;


		item[i].choose = i;


	}


	sort(item, 0, len);


	return len;


}





int main() {


	int N;


	long long V, ans = 0;


	cin>>N>>V;


	for (int i = 1; i<= N; ++i)


		cin>> v[i] >> w[i];


	int len1 = solve(1,N/2, itm[0]);


	int len2 = solve(N/2 + 1, N, itm[1]);


	for (int i= 1; i<= len2; ++i)


		itm[1][i].value=max(itm[1][i].value, itm[1][i-1].value);


	long long choose = 0;


	for (int i= 0; i<= len1; ++i) {


		while (len2 >= 0 && itm[0][i].value + itm[1][len2].value>V)


			--len2;


		if(len2>=0) {


			long long new_value = itm[0][i].weight + itm[1][len2].weight;


			long long new_choose = ___(5)___ ;


			if (ans == new_value)


				choose = max( choose, new_choose);


			if (ans < new_value) {


				ans = new_value ;


				choose = new_choose ;


			}


		}


	}


	cout<<ans<<endl;


	for (int i= 0; i< N; i++)


		if (choose & (1LL<<i))


			cout<<i+1<<' ';


	cout << endl;


}

选择题