经典的0-1背包问题。
代码中的backtracking部分是输出组成最大价值的编号。
// runtime: 4ms // space: 728K #include <iostream> #include <algorithm> #include <stack> using namespace std; int main() { int c, n; // c for count, n for number; while (cin>> c >> n) { int dp[n + 1][c + 1]; int price[n + 1], mark[n + 1]; for (int i = 1; i <= n; ++i) { cin >> price[i] >> mark[i]; } for (int i = 0; i <= n; ++i) { for (int j = 0; j <= c; ++j) { if (i == 0 || j == 0) { dp[i][j] = 0; continue; } if (j < price[i]) { dp[i][j] = dp[i - 1][j]; continue; } else { dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - price[i]] + mark[i]); } } } // output dp for (int i = 0; i <= n; ++i) { for (int j = 0; j <= c; ++j) { cout << dp[i][j] << " "; if (j == c) cout << endl; } } cout << dp[n][c] << endl; // Backtracking int row = n, col = c; stack<int> s; while (row > 0 && col > 0) { if (dp[row][col] == dp[row - 1][col]) { // not selected row--; continue; } else { // selected s.push(row); col -= price[row]; row--; } } while (!s.empty()) { cout << s.top() << endl; s.pop(); } } return 0; }
空间优化为一维数组。
// runtime: 4mm // space; 528K #include <iostream> #include <cstdio> #include <cstring> #include <algorithm> using namespace std; int main() { int c, n; // c for capacity, n for number while (scanf("%d %d", &c, &n) != EOF) { int V[n], P[n]; // V for value, P for Price for (int i = 0; i < n; ++i) { scanf("%d %d", &P[i], &V[i]); } int dp[c + 1]; memset(dp, 0, sizeof(dp)); // initialize dp. for (int i = 0; i < n; ++i) { for (int j = c; j >= P[i]; --j) { dp[j] = max(dp[j], dp[j - P[i]] + V[i]); } } printf("%d\n", dp[c]); } return 0; }