背包问题(backpack)的代码
时间: 2024-10-02 11:01:39 浏览: 2
背包问题是计算机科学中的经典问题,通常涉及选择物品以最大化价值,但又受限于某个容量限制。动态规划是最常见的解决策略,我们可以使用一个二维数组来存储当前状态(容量i和剩余价值j)下能获得的最大价值。
以下是一个简单的C++代码示例,用于解决0-1背包问题:
```cpp
#include <iostream>
using namespace std;
int knapsack(int W, int wt[], int val[], int n) {
int dp[n+1][W+1]; // dp[i][w]表示前i个物品,总重量不超过w时的最大价值
// 填充dp表
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 W = 50; // 容量
int wt[] = {10, 20, 30}; // 物品重量
int val[] = {60, 100, 120}; // 物品价值
int n = sizeof(wt) / sizeof(wt[0]);
cout << "最大价值为: " << knapsack(W, wt, val, n) << endl;
return 0;
}
```
这个代码定义了一个`knapsack`函数,它接受背包的容量、物品的重量数组、价值数组以及物品数量作为参数。`dp`数组是从左上角填充,根据当前物品是否可以放入决定是否选择它,然后计算最大价值。