背包九講之九：背包問題求具體方案
有 N 件物品和一個容量是 V 的背包。每件物品只能使用一次。
第 i 件物品的體積是 vi，價值是 wi。
求解將哪些物品裝入背包，可使這些物品的總體積不超過背包容量，且總價值最大。
輸出 字典序最小的方案。這里的字典序是指：所選物品的編號所構(gòu)成的序列。物品的編號范圍是 1…N。
輸入格式
第一行兩個整數(shù)，N，V，用空格隔開，分別表示物品數(shù)量和背包容積。
接下來有 N 行，每行兩個整數(shù) vi,wi，用空格隔開，分別表示第 i 件物品的體積和價值。
輸出格式
輸出一行，包含若干個用空格隔開的整數(shù)，表示最優(yōu)解中所選物品的編號序列，且該編號序列的字典序最小。
物品編號范圍是 1…N。
數(shù)據(jù)范圍
0<N,V≤1000
0<vi,wi≤1000
輸入樣例
4 5
1 2
2 4
3 4
4 6
輸出樣例
1 4
代碼如下：
1 #include<iostream> 2 #include<algorithm> 3 using namespace std; 4 const int n = 1002; 5 int N, V, v[n], w[n], f[n][n]; 6 int main() { 7 cin >> N >> V; 8 for (int i = 1; i <= N; ++i) 9 cin >> v[i] >> w[i]; 10 for (int i = N; i >= 1; --i) //倒著排，方便正著輸出物品序號 11 for (int j = 0; j <= V; ++j) { 12 f[i][j] = f[i + 1][j]; 13 if (j >= v[i]) 14 f[i][j] = max(f[i][j], f[i + 1][j - v[i]] + w[i]); 15 } 16 int vol = V; 17 for (int i = 1; i <= N; ++i) //正著輸出物品序號 18 if (vol >= v[i] && f[i][vol] == f[i + 1][vol - v[i]] + w[i]) { 19 cout << i << " "; 20 vol -= v[i]; 21 } 22 }
浙公網(wǎng)安備 33010602011771號