1 动态规划解决0/1背包问题 分数 100 作者 李丽娜 单位 吉林大学 现有n种物品,对1<=i<=n,第i种物品的重量为正整数w i ,价值为正整数p i ,背包能承受的最大载重量为正整数M,要求找出这n种物品的一个子集,使得子集中物品的总重量不超过M且总价值尽量大。0/1背包问题要求物品或者整件装入背包中,或者根本不装入(即不能装入物品的一部分),所以x i 限定只能取值0或1。 输入格式: 第1行是M和n,表示背包容量为M且有n件物品; 第2行是这n件物品的重量w i ; 第3行是各物品的价值p i ,背包容量和物品重量都为整数。 输出格式: 第1行是所选物品的价值之和,以及重量之和; 第2行是各物品装入背包的量,即x i 值。 输入样例1: 6 3 2 3 4 1 2 5 输出样例1: 6 6 1 0 1 输入样例2: 100 10 13 2 10 50 1 28 37 32 30 46 12 23 37 45 19 11 25 9 14 18 输出样例2: 149 100 0 1 1 1 1 0 1 0 0 0 代码长度限制 16 KB 时间限制 400 m
时间: 2024-03-12 19:49:50 浏览: 36
以下是动态规划的 C++ 代码实现:
```cpp
#include <iostream>
#include <cstring>
using namespace std;
const int N = 1010;
int M, n;
int w[N], p[N];
int m[N][N], x[N];
int main()
{
cin >> M >> n;
for (int i = 1; i <= n; i ++ ) cin >> w[i];
for (int i = 1; i <= n; i ++ ) cin >> p[i];
memset(m, 0, sizeof m);
for (int i = 1; i <= n; i ++ )
for (int j = w[i]; j <= M; j ++ )
m[i][j] = max(m[i - 1][j], m[i - 1][j - w[i]] + p[i]);
int sumv = m[n][M];
int sumw = 0;
for (int i = n; i >= 1; i -- )
if (m[i][M] != m[i - 1][M])
{
x[i] = 1;
sumw += w[i];
M -= w[i];
}
cout << sumv << ' ' << sumw << endl;
for (int i = 1; i <= n; i ++ ) cout << x[i] << ' ';
return 0;
}
```
时间复杂度:$O(nM)$,空间复杂度:$O(nM)$。
相关推荐
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![application/x-rar](https://img-home.csdnimg.cn/images/20210720083606.png)
![rar](https://img-home.csdnimg.cn/images/20210720083606.png)
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)
![txt](https://img-home.csdnimg.cn/images/20210720083642.png)
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)
![7z](https://img-home.csdnimg.cn/images/20210720083312.png)
![7z](https://img-home.csdnimg.cn/images/20210720083312.png)
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)
![7z](https://img-home.csdnimg.cn/images/20210720083312.png)
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)
![7z](https://img-home.csdnimg.cn/images/20210720083312.png)
![7z](https://img-home.csdnimg.cn/images/20210720083312.png)