背包 C++
时间: 2023-07-07 18:10:42 浏览: 43
C++中背包(Knapsack)问题的常见解法有动态规划和回溯法,这里分别给出代码实现。
动态规划解法:
```c++
#include<iostream>
#include<algorithm>
using namespace std;
int knapsack(int W, int wt[], int val[], int n) {
int dp[n+1][W+1];
for (int i = 0; i <= n; i++) {
for (int w = 0; w <= W; w++) {
if (i == 0 || w == 0) {
dp[i][w] = 0;
} else 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 val[] = {60, 100, 120};
int wt[] = {10, 20, 30};
int W = 50;
int n = sizeof(val) / sizeof(val[0]);
cout << knapsack(W, wt, val, n);
return 0;
}
```
回溯法解法:
```c++
#include<iostream>
using namespace std;
int n = 3, W = 50;
int val[] = {60, 100, 120};
int wt[] = {10, 20, 30};
int maxVal = 0;
void knapsack(int i, int w, int v) {
if (i == n) {
maxVal = max(maxVal, v);
return;
}
if (w + wt[i] <= W) {
knapsack(i+1, w+wt[i], v+val[i]); // 把第i个物品放进去
}
knapsack(i+1, w, v); // 不把第i个物品放进去
}
int main() {
knapsack(0, 0, 0);
cout << maxVal;
return 0;
}
```
背包问题的解法可以参考其他教程,这里只是提供一种C++实现。