第六章上机实验报告
7-1 0-1背包 (20 分)
给定n(n<=100)种物品和一个背包。物品i的重量是wi，价值为vi，背包的容量为C(C<=1000)。问:应如何选择装入背包中的物品，使得装入背包中物品的总价值最大? 在选择装入背包的物品时，对每种物品i只有两个选择：装入或不装入。不能将物品i装入多次，也不能只装入部分物品i。
输入格式:
共有n+1行输入： 第一行为n值和c值，表示n件物品和背包容量c； 接下来的n行，每行有两个数据，分别表示第i(1≤i≤n)件物品的重量和价值。
输出格式:
输出装入背包中物品的最大总价值。
输入样例:
5 10
2 6
2 3
6 5
5 4
4 6
结尾无空行
输出样例:
15
一、问题分析：
本题诗要求解在不超过背包总容量的前提下使得背包中物品价值达到最大，本题诗通过广度优先的方式遍历解空间树来解决此问题的，要通过广度优先的方式求解改的问题则要把要进行广度优先遍历的节点先保存在队列中，进而求解，当遍历到叶子节点时，把该节点从队列中移除，并记录下一个解，最后保存的解即为最优解。
二、代码
#include <iostream>
#include <queue>
using namespace std;
struct Node{
int cv;
int cw;
int level;
};
struct Obj{
int weight;
int value;
}Objs[100];
queue<Node> q;
int bestv;
int n,c;
void dp(){
Node root;
root.cv = 0;
root.cw = 0;
root.level = 1;
q.push(root);
while(!q.empty()){
Node parent = q.front();
q.pop();
if(parent.level>n){
if(parent.cv>bestv){
bestv = parent.cv;
}
}else{
if(parent.cw+Objs[parent.level].weight<=c){
Node lchild;
lchild.cv = parent.cv+Objs[parent.level].value;
lchild.cw = parent.cw+Objs[parent.level].weight;
lchild.level = parent.level +1;
q.push(lchild);
}
Node rchild;
rchild.cv = parent.cv;
rchild.cw = parent.cw;
rchild.level = parent.level +1;
q.push(rchild);
}
}
}
int main(int argc, char** argv) {
cin>>n>>c;
for(int i=1;i<=n;i++){
cin>>Objs[i].weight>>Objs[i].value;
}
dp();
cout<<bestv<<endl;
return 0;
}
三、实验心得
广度优先算法要求我们要对遍历解空间树有一个很清晰的理解，根据这个理解我们才能把代码相应遍历的部分写正确。广度优先方法也为求解一些问题提供了另一种解决方案。