不是VIP会员,不能显示答案

题目解答

题目:
(背包问题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;

}




选择题

1) ⑴处应填( )。

2) ⑵处应填( )。

3) ⑶处应填( )。

4) ⑷处应填( )。

5) ⑸处应填( )。
考点:
分析:
解答:
评论:
老师: