第1页 / 共12页
第2页 / 共12页
第3页 / 共12页
第4页 / 共12页
第5页 / 共12页
第6页 / 共12页
第7页 / 共12页
第8页 / 共12页
0-1背包问题（分支限界法）报告.doc
实验十六：0-1背包问题（分支限界法）报告
1．问题描述
2．实验目的
3．实验原理
4．实验设计
5．实验结果与分析
6．结论
7．程序源码
实验十六：0-1 背包问题（分支限界法）报告
2017061111 李静娴
1．问题描述
给定 n 种物品和一背包。物品 i 的重量是 wi，其价值为 vi，背包的容量为 C。问:应如何选择
装入背包的物品，使得装入背包中物品的总价值最大?
2．实验目的
（1）熟悉分支限界法，并学以致用
（2）熟练掌握 0-1 背包问题算法
3．实验原理
首先，要对输入数据进行预处理，将各物品依其单位重量价值从大到小进行排列。在优
先队列分支限界法中，节点的优先级由已装袋的物品价值加上剩下的最大单位重量价值的物
品装满剩余容量的价值和。
算法首先检查当前扩展结点的左儿子结点的可行性。如果该左儿子结点是可行结点，则
将它加入到子集树和活结点优先队列中。当前扩展结点的右儿子结点一定是可行结点，仅当
右儿子结点满足上界约束时才将它加入子集树和活结点优先队列。当扩展到叶节点时为问题
的最优值。
算法的时间复杂度： O(2^n)。
4．实验设计
（1）
输入数据格式：宏定义集装箱个数 n，背包容量以及物品质量和价值由用户自定义
生成方式：用户输入
数据规模：宏定义设定。
（2）
该程序先是设定好物品个数，然后由用户设定背包容量以及物品的质量和价值。再调用
Knapsack(p, w, c, n)函数输出背包能装下的最大价值。bestx[i]输出最优解。
（3）
程序运行的结果有四部分，先是输出背包容量，再输出物品重量和价值，然后输出背包
能装的最大价值，最后输出最优解。
5．实验结果与分析
经过调用 Knapsack(p, w, c, n)函数输出背包能装下的最大价值。bestx[i]输出最优解。
经人工分析，所得结果与程序运算一致，可见程序计算结果无误。
6．结论
用户可以自定义背包容量，物品质量和价值，使得程序具有很好的交互性。本来打算让
物品个数也动态生成，用堆的方式可以实现，但是考虑到这将增加代码工程量，本程序已经
能够很好的实现算法了，而且已经具有很强的交互性了，暂时先没有实现这个功能，留待以
后改进。
7．程序源码
1、 MaxHeap.h
#include
using namespace std;
template
class MaxHeap
{
public:
MaxHeap(int MaxHeapSize = 10);
~MaxHeap() { delete[] heap; }
int Size() const { return CurrentSize; }
T Max()
{
//查
return heap[1];
}
MaxHeap& Insert(const T& x); //增
MaxHeap& DeleteMax(T& x);
//删
void Initialize(T a[], int size, int ArraySize);
private:
int CurrentSize, MaxSize;
T *heap;
// element array
};
template
MaxHeap::MaxHeap(int MaxHeapSize)
{// Max heap constructor.
MaxSize = MaxHeapSize;
heap = new T[MaxSize + 1];
CurrentSize = 0;
}
template
MaxHeap& MaxHeap::Insert(const T& x)
{// Insert x into the max heap.
if (CurrentSize == MaxSize)
{
cout << "no space!" << endl;
return *this;
}
// 寻找新元素 x 的位置
// i——初始为新叶节点的位置，逐层向上，寻找最终位置
int i = ++CurrentSize;
while (i != 1 && x > heap[i / 2])
{
// i 不是根节点，且其值大于父节点的值，需要继续调整
heap[i] = heap[i / 2]; // 父节点下降
i /= 2;
// 继续向上，搜寻正确位置
}
heap[i] = x;
return *this;
}
template
MaxHeap& MaxHeap::DeleteMax(T& x)
{// Set x to max element and delete max element from heap.
// check if heap is empty
if (CurrentSize == 0)
{
cout << "Empty heap!" << endl;
return *this;
}
x = heap[1]; // 删除最大元素
// 重整堆
T y = heap[CurrentSize--]; // 取最后一个节点，从根开始重整
// find place for y starting at root
int i = 1,
// current node of heap
ci = 2; // child of i
while (ci <= CurrentSize)
{
// 使 ci 指向 i 的两个孩子中较大者
if (ci < CurrentSize && heap[ci] < heap[ci + 1])
{
ci++;
}
// y 的值大于等于孩子节点吗？
if (y >= heap[ci])
{
break;
// 是，i 就是 y 的正确位置，退出
}
// 否，需要继续向下，重整堆
heap[i] = heap[ci]; // 大于父节点的孩子节点上升
i = ci;
ci *= 2;
// 向下一层，继续搜索正确位置
}
heap[i] = y;
return *this;
}
template
void MaxHeap::Initialize(T a[], int size, int ArraySize)
{// Initialize max heap to array a.
delete[] heap;
heap = a;
CurrentSize = size;
MaxSize = ArraySize;
// 从最后一个内部节点开始，一直到根，对每个子树进行堆重整
for (int i = CurrentSize / 2; i >= 1; i--)
{
T y = heap[i]; // 子树根节点元素
// find place to put y
int c = 2 * i; // parent of c is target
// location for y
while (c <= CurrentSize)
{
// heap[c] should be larger sibling
if (c < CurrentSize && heap[c] < heap[c + 1])
{
c++;
}
// can we put y in heap[c/2]?
if (y >= heap[c])
{
break;
// yes
}
// no
heap[c / 2] = heap[c]; // move child up
c *= 2; // move down a level
}
heap[c / 2] = y;
}
}
2、 Knapsack.cpp
#include "MaxHeap.h"
#include
using namespace std;
class Object
{
template
friend Typep Knapsack(Typep p[], Typew w[], Typew c, int n, int bestx[]);
public:
int operator <= (Object a) const
{
return d >= a.d;
}
private:
int ID;
float d;//单位重量价值
};
template class Knap;
class bbnode
{
friend Knap;
template
friend Typep Knapsack(Typep p[], Typew w[], Typew c, int n, int bestx[]);
private:
bbnode * parent;
bool LChild;
//指向父节点的指针
//左儿子节点标识
};
template
class HeapNode
{
friend Knap;
public:
operator Typep() const
{
return uprofit;
}
private:
Typep uprofit,
profit;
Typew weight;
int level;
bbnode *ptr;
//节点的价值上界
//节点所相应的价值
//节点所相应的重量
//活节点在子集树中所处的层序号
//指向活节点在子集中相应节点的指针
};
template
class Knap
{
template
friend Typep Knapsack(Typep p[], Typew w[], Typew c, int n, int bestx[]);
public:
Typep MaxKnapsack();
private:
MaxHeap> *H;
Typep Bound(int i);
void AddLiveNode(Typep up, Typep cp, Typew cw, bool ch, int lev);
bbnode *E;
Typew c;
int n;
//指向扩展节点的指针
//背包容量
//物品数
Typew *w;
Typep *p;
Typew cw;
//物品重量数组
//物品价值数组
//当前重量
Typep cp;
int *bestx; //最优解
//当前价值
};
template
inline void Swap(Type &a, Type &b);
template
void BubbleSort(Type a[], int n);
int main()
{
const int n = 4;//物品数
int c;//背包容量
int p[n + 1];
int w[n + 1];
cout << "物品数：" <> c;
cout << "输入物品价值：" << endl;
for (int i = 1; i <= n; i++) {
cin >> p[i];//物品价值 下标从 1 开始
}
cout << endl;
cout << "输入物品重量：" << endl;
for (int i = 1; i <= n; i++) {
cin >> w[i];//物品重量 下标从 1 开始
}
cout << endl;
int bestx[n+1];//最优解
cout << "背包容量为：" << c << endl;
cout << "物品重量和价值分别为：" << endl;
for (int i = 1; i <= n; i++)
{
cout << "(" << w[i] << "," << p[i] << ") ";
}
cout << endl;
cout << "背包能装下的最大价值为：" << Knapsack(p, w, c, n, bestx) << endl;
cout << "此背包问题最优解为:" << endl;
for (int i = 1; i <= n; i++)
{
cout << bestx[i] << " ";
}
cout << endl;
return 0;
}
template
Typep Knap::Bound(int i)//计算节点所相应价值的上界
{
//价值上界
//剩余容量高
Typew cleft = c - cw;
Typep b = cp;
//以物品单位重量价值递减序装填剩余容量
while (i <= n && w[i] <= cleft)
{
cleft -= w[i];
相关推荐
2023年江西萍乡中考道德与法治真题及答案.doc
2012年重庆南川中考生物真题及答案.doc
2013年江西师范大学地理学综合及文艺理论基础考研真题.doc
2020年四川甘孜小升初语文真题及答案I卷.doc
2020年注册岩土工程师专业基础考试真题及答案.doc
2023-2024学年福建省厦门市九年级上学期数学月考试题及答案.doc
2021-2022学年辽宁省沈阳市大东区九年级上学期语文期末试题及答案.doc
2022-2023学年北京东城区初三第一学期物理期末试卷及答案.doc
2018上半年江西教师资格初中地理学科知识与教学能力真题及答案.doc
2012年河北国家公务员申论考试真题及答案-省级.doc
2020-2021学年江苏省扬州市江都区邵樊片九年级上学期数学第一次质量检测试题及答案.doc
2022下半年黑龙江教师资格证中学综合素质真题及答案.doc
