http://acm.bnu.edu.cn/bnuoj/problem_show.php?pid=4183
初学 0/1 背包，准备开始看背包.....
View Code
1 #include <iostream> 2 #define maxn 1001 3 using namespace std; 4 int f[maxn][maxn], v[maxn], w[maxn], mark[maxn]; 5 int main() 6 { 7 int i, j, n, m, l, now; 8 cin >> n >> m; 9 for(i = 0; i <= n; i++) 10 for(j = 0; j <= m; j++) 11 f[i][j] = 0; 12 for(i = 1; i <= n; i++) 13 cin >> v[i] >> w[i]; 14 l = 0; 15 for(i = 1; i <= n; i++) 16 { 17 for(j = 0; j <= m; j++) 18 { 19 f[i][j] = f[i-1][j]; 20 if( v[i] <= j && f[i-1][j-v[i]]+w[i] > f[i][j]) 21 f[i][j] = f[i-1][j-v[i]]+w[i]; 22 } 23 } 24 j = m; 25 for(i = n; i >= 1; i--) 26 { 27 if(f[i][j] > f[i-1][j]) 28 { 29 mark[l++] = i; 30 j -= v[i]; 31 } 32 } 33 cout << f[n][m] << endl; 34 for(i = 0; i < l; i++) 35 { 36 if(i == l-1) cout << mark[i]-1 << endl; 37 else cout << mark[i]-1 << " "; 38 } 39 return 0; 40 }