3.编写算法,求解下列背包问题 有3个物体,重量和价值分别为W=[3,4,5]和P=[6,12,20]背包载重量M=10。C++
时间: 2024-02-22 12:55:29 浏览: 16
好的,以下是 C++ 实现的背包问题求解算法,基于动态规划思想:
```cpp
#include <iostream>
#include <algorithm>
using namespace std;
int knapsack(int w[], int p[], int n, int m) {
int dp[n + 1][m + 1]; // dp[i][j] 表示前 i 个物品在背包容量为 j 时的最大价值
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 - 1] <= j) {
dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - w[i - 1]] + p[i - 1]);
} else {
dp[i][j] = dp[i - 1][j];
}
}
}
return dp[n][m];
}
int main() {
int w[] = {3, 4, 5};
int p[] = {6, 12, 20};
int m = 10;
int n = sizeof(w) / sizeof(w[0]);
int maxVal = knapsack(w, p, n, m);
cout << "最大价值为:" << maxVal << endl;
return 0;
}
```
在给定的背包问题中,使用动态规划算法可以得到最大价值为 32。