c++动态规划实现0-1背包问题
时间: 2023-11-13 19:54:21 浏览: 61
0-1背包问题是一个经典的动态规划问题,可以使用动态规划算法来解决。具体实现步骤如下:
1. 定义状态:设 dp[i][j] 表示前 i 个物品放入容量为 j 的背包中所能获得的最大价值。
2. 初始化状态:dp[j] = 0,dp[i] = 0。
3. 状态转移方程:对于第 i 个物品,有两种情况:
a. 不放入背包中,此时 dp[i][j] = dp[i-1][j];
b. 放入背包中,此时 dp[i][j] = dp[i-1][j-w[i]] + v[i],其中 w[i] 表示第 i 个物品的重量,v[i] 表示第 i 个物品的价值。
综上所述,状态转移方程为:dp[i][j] = max(dp[i-1][j], dp[i-1][j-w[i]] + v[i])。
4. 最终结果:dp[n][m],其中 n 表示物品的数量,m 表示背包的容量。
下面是 C++ 的实现代码:
```c++
#include <iostream>
#include <cstring>
using namespace std;
const int N = 1010;
int n, m;
int w[N], v[N];
int dp[N][N];
int main()
{
cin >> n >> m;
for (int i = 1; i <= n; i++) cin >> w[i] >> v[i];
memset(dp, 0, sizeof dp);
for (int i = 1; i <= n; i++)
for (int j = 1; j <= m; j++)
{
dp[i][j] = dp[i-1][j];
if (j >= w[i]) dp[i][j] = max(dp[i][j], dp[i-1][j-w[i]] + v[i]);
}
cout << dp[n][m] << endl;
return 0;
}
```