简单0,1背包哦问题代码实现
时间: 2023-06-06 21:06:45 浏览: 60
好的,关于简单的0-1背包问题,以下是一个可能的代码实现:
```
#include <iostream>
#include <vector>
using namespace std;
int knapsack(int W, vector<int>& wt, vector<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() {
vector<int> wt {1, 3, 4, 5};
vector<int> val {1, 4, 5, 7};
int W = 7;
int n = wt.size();
cout << knapsack(W, wt, val, n) << endl;
return 0;
}
```
这个代码实现采用了动态规划算法,其时间复杂度为 O(nW),其中 n 是物品的数量,W 是背包的容量。这个算法的主要思路是,构建一个二维数组 dp[i][w],表示前 i 个物品中,容量为 w 的背包能够装下的最大价值。根据背包问题的性质,对于每一个物品,都有两种选择:放入背包和不放入背包。因此可以通过递推式 dp[i][w]=max(val[i-1]+dp[i-1][w-wt[i-1]], dp[i-1][w]) 来计算 dp 数组的值。
在上述实现中,已经预设了一组输入数据,其中物品的重量和价值分别为 {1, 3, 4, 5} 和 {1, 4, 5, 7},背包的容量为 7。程序输出的结果为 9,表示最大价值为 9。
希望这个代码实现能够帮助到您。
相关推荐
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)
![cpp](https://img-home.csdnimg.cn/images/20210720083646.png)
![-](https://img-home.csdnimg.cn/images/20210720083327.png)
![-](https://img-home.csdnimg.cn/images/20210720083327.png)
![-](https://img-home.csdnimg.cn/images/20210720083327.png)
![-](https://img-home.csdnimg.cn/images/20210720083327.png)
![-](https://img-home.csdnimg.cn/images/20210720083327.png)
![-](https://csdnimg.cn/download_wenku/file_type_column_c1.png)
![-](https://csdnimg.cn/download_wenku/file_type_column_c1.png)
![-](https://csdnimg.cn/download_wenku/file_type_column_c1.png)
![-](https://csdnimg.cn/download_wenku/file_type_column_c1.png)
![-](https://csdnimg.cn/download_wenku/file_type_column_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)