查看题目

Notice: Undefined index: name in /usr/www/lib/views/home/viewtitle.html on line 188
-完善程序第 20 题

(背包问题2)有N(O

#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;
}

● 单选题

第 1 题 ⑴处应填( )。

第 2 题 ⑵处应填( )。

第 3 题 ⑶处应填( )。

第 4 题 ⑷处应填( )。

第 5 题 ⑸处应填( )。

解答部分以后会开放。