用c++写01背包问题代码
时间: 2023-04-08 18:04:01 浏览: 76
以下是用 C 语言写的 01 背包问题代码:
```c
#include <stdio.h>
#define MAX_N 100
#define MAX_W 1000
int N, W;
int w[MAX_N], v[MAX_N];
int dp[MAX_N+1][MAX_W+1];
int max(int a, int b) {
return a > b ? a : b;
}
int main() {
scanf("%d %d", &N, &W);
for (int i = 0; i < N; i++) {
scanf("%d %d", &w[i], &v[i]);
}
for (int i = 0; i < N; i++) {
for (int j = 0; j <= W; j++) {
if (j < w[i]) {
dp[i+1][j] = dp[i][j];
} else {
dp[i+1][j] = max(dp[i][j], dp[i][j-w[i]] + v[i]);
}
}
}
printf("%d\n", dp[N][W]);
return 0;
}
```
这个代码实现了 01 背包问题的动态规划算法,可以计算出在给定的物品重量和价值下,背包能够装下的最大价值。
相关问题
用c++写01背包问题
以下是使用动态规划思想,用C++实现01背包问题的代码:
```cpp
#include <iostream>
#include <cstring>
using namespace std;
int main()
{
int n, W;
cin >> n >> W; // n表示物品数量,W表示背包容量
int w[n+1], v[n+1];
for (int i = 1; i <= n; i++) {
cin >> w[i] >> v[i]; // 输入每个物品的重量和价值
}
int dp[n+1][W+1];
memset(dp, 0, sizeof(dp)); // 初始化dp数组
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= W; j++) {
if (j >= w[i]) {
dp[i][j] = max(dp[i-1][j], dp[i-1][j-w[i]] + v[i]); // 状态转移方程
}
else {
dp[i][j] = dp[i-1][j];
}
}
}
cout << dp[n][W] << endl; // 输出最大价值
return 0;
}
```
输入样例:
```
4 5
2 3
1 2
3 4
2 2
```
输出样例:
```
7
```
其中,dp[i][j]表示前i个物品放入容量为j的背包中所能获得的最大价值。状态转移方程为:
dp[i][j] = max(dp[i-1][j], dp[i-1][j-w[i]] + v[i])
其中,dp[i-1][j]表示不选择第i个物品时的最大价值,dp[i-1][j-w[i]] + v[i]表示选择第i个物品时的最大价值。如果背包容量j小于当前物品重量w[i],则无法放入背包中,此时dp[i][j]等于dp[i-1][j]。最终输出dp[n][W]即为所求的最大价值。
C++01背包问题代码
C++中的01背包问题是一个经典的动态规划问题,它的目标是在给定的一组物品中选择一些物品放入背包,使得物品的总价值最大,同时要保证背包的容量不超过限制。
以下是一个简单的C++代码示例来解决01背包问题:
```cpp
#include <iostream>
#include <vector>
using namespace std;
int knapsack(int W, vector<int>& wt, vector<int>& val, int n) {
vector<vector<int>> dp(n + 1, vector<int>(W + 1, 0));
for (int i = 1; i <= n; i++) {
for (int w = 1; w <= W; w++) {
if (wt[i - 1] <= w) {
dp[i][w] = max(val[i - 1] + dp[i - 1][w - wt[i - 1]], dp[i - 1][w]);
} else {
dp[i][w] = dp[i - 1][w];
}
}
}
return dp[n][W];
}
int main() {
int W = 10; // 背包容量
vector<int> wt = {2, 3, 4, 5}; // 物品重量
vector<int> val = {3, 4, 5, 6}; // 物品价值
int n = wt.size(); // 物品数量
int maxVal = knapsack(W, wt, val, n);
cout << "背包能装下的最大价值为:" << maxVal << endl;
return 0;
}
```
这段代码中,我们使用一个二维数组`dp`来记录每个状态下的最大价值。其中`dp[i][w]`表示前`i`个物品在背包容量为`w`时的最大价值。通过动态规划的思想,我们可以逐步计算出`dp[n][W]`,即背包能装下的最大价值。