用C++实现一个背包问题
时间: 2024-05-07 17:20:02 浏览: 10
背包问题是一个经典的动态规划问题,可以用C++实现。下面是一个简单的背包问题代码实现,可以参考一下:
```c++
#include <iostream>
#include <algorithm>
using namespace std;
int main()
{
int n, m;
cin >> n >> m;
int w[n+1], v[n+1];
for(int i = 1; i <= n; i++)
{
cin >> w[i] >> v[i];
}
int dp[n+1][m+1];
for(int i = 0; i <= n; i++)
{
for(int j = 0; j <= m; j++)
{
if(i == 0 || j == 0)
{
dp[i][j] = 0;
}
else if(w[i] > j)
{
dp[i][j] = dp[i-1][j];
}
else
{
dp[i][j] = max(dp[i-1][j], dp[i-1][j-w[i]]+v[i]);
}
}
}
cout << dp[n][m] << endl;
return 0;
}
```
其中,输入的第一行包括两个整数,分别表示物品数量和背包容量;接下来的n行每行包括两个整数,分别表示物品的重量和价值。最后输出最大价值。