函数题：0/1背包问题 （队列式广度优先搜索）

有n个重量分别为{w1，w2，…，wn}的物品，它们的价值分别为{v1，v2，…，vn}，给定一个载重限制为W的背包。

设计从这些物品中选取一部分物品放入该背包的方案，每个物品要么不选中要么选中一次，求取满足总重量不大于W并且具有最大价值的物品装入方案。

### 函数接口定义：
c++
void EnQueue(NodeType e, queue<NodeType> &qu); //结点e是否进队qu以及相应处理
void bfs(); //广度优先搜索最优解


### 裁判测试程序样例：
c++
#include <iostream>
#include <queue>
#include <vector>

using namespace std;

int maxv = 0; //存放最大价值,初始为最小值
vector<int> bestx; //存放最优解,全局变量

int n, W; // n:物品数量，W:重量限制
vector<int> w; // 各个物品重量
vector<int> v; // 各个物品价值

struct NodeType //队列中的结点类型
{
int i; //当前结点在搜索空间中的层次
int w; //当前结点的总重量
int v; //当前结点的总价值
vector<int> x; //当前结点包含的解向量,若x为{1,0,0,1}，表示子集中只有有第1个和第4个物品
};

void EnQueue(NodeType e, queue<NodeType> &qu); //结点e是否进队qu以及相应处理
void bfs(); //广度优先搜索最优解

int main()
{
int iw, iv, i;

cin >> n >> W;

for(i = 0; i < n; i++){
cin >> iw >> iv;
w.push_back(iw);
v.push_back(iv);
}

bfs(); // 广度优先搜索

cout<<maxv<<endl;

return 0;
}


/* 请在这里填写答案 */


### 输入样例：

第一行是物品数目n和总重量限制W
之后n行分别是各个物品的重量和价值

in
3 30
16 45
15 25
15 25


### 输出样例：

物品最优装载方案得到最大总价值

out
50







答案：若无答案欢迎评论