动态规划0-1背包问题

0-1背包问题是动态规划的经典问题之一，它的问题描述如下：

有n个物品和一个容量为W的背包。每个物品有一个重量和一个价值，要求选择一些物品装入背包，使得装入背包中物品的总重量不超过W，且价值最大。其中每种物品只有一个，可以选择装入或不装入。

动态规划思路：

设f[i][j]表示前i个物品，背包容量为j时可以获得的最大价值。

则有以下状态转移方程：

1. 不选第i个物品：f[i][j] = f[i-1][j]
2. 选第i个物品：f[i][j] = f[i-1][j-w[i]] + v[i]

其中，w[i]表示第i个物品的重量，v[i]表示第i个物品的价值。

因此，最终的结果为f[n][W]，即前n个物品，背包容量为W时可以获得的最大价值。

代码实现：

int dp[MAXN][MAXW]; // dp数组
int w[MAXN], v[MAXN]; // 物品重量和价值
int n, W; // 物品数量和背包容量

int knapsack() {
// 初始化dp数组
for(int i=0; i<=n; i++) {
dp[i][0] = 0;
}
for(int j=0; j<=W; j++) {
dp[0][j] = 0;
}
// 动态规划过程
for(int i=1; i<=n; i++) {
for(int j=1; j<=W; j++) {
if(j-w[i] < 0) {
dp[i][j] = dp[i-1][j];
}
else {
dp[i][j] = max(dp[i-1][j], dp[i-1][j-w[i]] + v[i]);
}
}
}
// 返回结果
return dp[n][W];
}