两种0-1背包的动态规划解决方法。下面第一种可以获得最优解，但是占空间，第二种节省空间。状态转移方程见函数
例题参见poj3624
#define _CRT_SECURE_NO_WARNINGS #include <iostream> #include <cstdio> #include <cmath> #include <cstdlib> #include <cstring> #include <climits> #include <stack> #include <queue> #include <vector> #include <string> #include <map> #include <set> #include <algorithm> using namespace std; /*------default---------*/ const int maxn = 4 * 1e3 + 7; int v[maxn], w[maxn], dp[maxn][maxn]; //max(m(i + 1, j), m(i + 1, j - w[i]) + vi); j >= w[i] 当背包装得下w[i]，不装 or 装 ？ void Knapsack(int value[], int weght[], int c, int n, int m[][maxn]) { //m[i][j]表示背包容量为j，可选物品为[i:n]时0-1背包的最优值 int jMax = min(weght[n] - 1, c); for (int j = 0; j <= jMax; ++j) m[n][j] = 0; for (int j = weght[n]; j <= c; ++j) m[n][j] = value[n]; for (int i = n - 1; i >= 1; --i) { int jMax = min(weght[i] - 1, c); for (int j = 0; j <= jMax; ++j) m[i][j] = m[i + 1][j]; for (int j = weght[i]; j <= c; ++j) m[i][j] = max(m[i + 1][j], m[i + 1][j - weght[i]] + value[i]); } } void Traceback(int m[][maxn], int w[], int c, int n, int x[]) { for (int i = 1; i < n; ++i) { if (m[i][c] == m[i + 1][c]) x[i] = 0; else { x[i] = 1; c -= w[i]; } x[n] = m[n][c] ? 1 : 0; } } int main() { int n, c; while (~scanf("%d%d", &n, &c)) { for (int i = 1; i <= n; ++i) scanf("%d%d", w + i, v + i); Knapsack(v, w, c, n, dp); printf("%d\n", dp[1][c]); } return 0; }void Knapsack(int w[], int v[], int n, int c, int dp[]) { memset(dp, 0, sizeof dp); for (int i = 1; i <= n; ++i) for (int j = c; j >= w[i]; --j) dp[j] = max(dp[j], dp[j - w[i]] + v[i]); }//dp[j]表示背包容量为j时0-1背包的最优价值。数组范围为背包容量。 # by wjqin
