用c++写简单的背包问题。设有一个背包,可以放入的重量为s。现有n件物品,重量分别为w1,w2…,wn,(1≤i≤n)均为正整数,从n件物品中挑选若干件,使得放入背包的重量之和正好为s。
时间: 2024-02-12 15:03:07 浏览: 89
好的,我可以帮您写一个简单的背包问题的代码。这里我使用动态规划的方法。
```c++
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int main()
{
int s = 10; // 背包容量
int n = 5; // 物品数量
vector<int> w = {3, 4, 2, 5, 1}; // 物品重量
// 初始化动态规划数组
vector<vector<bool>> dp(n+1, vector<bool>(s+1, false));
for (int i = 0; i <= n; i++) {
dp[i][0] = true;
}
// 动态规划求解
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= s; j++) {
if (j - w[i-1] >= 0) {
dp[i][j] = dp[i-1][j] || dp[i-1][j-w[i-1]];
} else {
dp[i][j] = dp[i-1][j];
}
}
}
// 输出结果
if (dp[n][s]) {
cout << "可以放入背包的重量之和正好为" << s << endl;
} else {
cout << "无法放入背包的重量之和正好为" << s << endl;
}
return 0;
}
```
这段代码中,我们定义了背包容量`s`为10,物品数量`n`为5,物品重量`w`为{3, 4, 2, 5, 1}。首先初始化一个二维的动态规划数组`dp`,其中`dp[i][j]`表示前`i`件物品能否凑出重量为`j`。然后,我们先将`dp[0][j]`都初始化为`true`(因为前0件物品可以凑出重量为0),然后按照动态规划的思路,依次求解`dp[i][j]`。
最后,我们判断`dp[n][s]`的值,如果为`true`,则说明可以放入背包的重量之和正好为`s`,否则无法凑出。
阅读全文