题目描述:有N个物品,每个物品的重量是wi ,每个物品的价值是vi 。 求解当背包容量为W时,能获得的最大价值,并输出获得最大价值时每种物品是否在背包内 数据范围 0 < n <= 30 重量、价值、背包容量均为正整数 。输入: 第一行两个数,N和W,N表示物品的个数,W表示容量限制 接下来N行,每行两个数,分别是wi和vi,分别表示第i个物品的重量和价值 。输出: 第一行一个数,为最大价值 第二行N个数,依次表示各个物品的是否放在背包里(0表示不放,1表示放),如果有多种方案,取字典序。请提供c++代码解决这题
时间: 2023-09-21 08:06:21 浏览: 78
以下是动态规划的思路,时间复杂度为O(NW),可以通过本题。
```c++
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 35, M = 1e5 + 5;
int n, m;
int w[N], v[N];
int f[M], g[M];
int main()
{
cin >> n >> m;
for(int i = 1; i <= n; i++) cin >> w[i] >> v[i];
for(int i = 1; i <= n; i++)
for(int j = m; j >= w[i]; j--)
{
if(f[j - w[i]] + v[i] > f[j])
{
f[j] = f[j - w[i]] + v[i];
g[j] = g[j - w[i]];
g[j] |= 1 << (i - 1); // 将第i个物品放入背包
}
else if(f[j - w[i]] + v[i] == f[j])
{
g[j] = min(g[j], g[j - w[i]] | (1 << (i - 1))); // 取字典序最小的方案
}
}
cout << f[m] << endl;
for(int i = 0; i < n; i++)
cout << ((g[m] >> i) & 1) << " ";
return 0;
}
```