01背包问题动态规划c++
时间: 2023-07-07 22:37:12 浏览: 48
下面是一个基于C++的01背包问题动态规划的实现示例:
```c++
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int main()
{
int n, C;
cin >> n >> C;
vector<int> w(n+1); // 物品重量
vector<int> v(n+1); // 物品价值
for(int i = 1; i <= n; i++)
{
cin >> w[i] >> v[i];
}
vector<int> dp(C+1); // 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]);
}
}
cout << dp[C] << endl;
return 0;
}
```
在上面的代码中,我们使用了vector来存储物品的重量和价值,使用一维数组dp来存储最大价值,并且使用了逆序枚举的方式来更新dp数组,以避免重复选择同一个物品。
相关问题
01背包问题动态规划C++
01背包问题是一种经典的动态规划问题,它的目标是在背包容量一定的情况下,选择不同的物品,使得装入背包中的物品总价值最大。C++实现的思路如下:
1.定义一个dp数组,其中dp[i][j]表示容量为j时前i个物品的最大价值。
2.使用for循环遍历每一个物品,再使用另一个for循环遍历每一个容量,通过比较是否将当前物品放入背包中能够获得更大的价值,来更新dp数组中对应位置的值。
3.最后dp[n][V]就是容量为V时前n个物品的最大价值。
以下是C++代码实现:
```
int knapsack(int V, int n, int* w, int* v) {
int dp[n + 1][V + 1];
memset(dp, 0, sizeof(dp));
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= V; j++) {
if (w[i - 1] > j) {
dp[i][j] = dp[i - 1][j];
} else {
dp[i][j] = max(dp[i - w[i - 1]] + v[i - 1]);
}
}
}
return dp[n][V];
}
```
01背包问题动态规划 c++
好的,针对您的问题,以下是 01 背包问题的动态规划解法的 C++ 代码:
```c++
#include <iostream>
#include <cstring>
using namespace std;
const int N = 1010;
int n, m;
int v[N], w[N];
int f[N][N];
int main()
{
cin >> n >> m;
for (int i = 1; i <= n; i ++ ) cin >> v[i] >> w[i];
for (int i = 1; i <= n; i ++ )
for (int j = 0; j <= m; j ++ )
{
f[i][j] = f[i - 1][j];
if (j >= v[i]) f[i][j] = max(f[i][j], f[i - 1][j - v[i]] + w[i]);
}
cout << f[n][m] << endl;
return 0;
}
```