#include "DKnapsack.h"
#include <queue>
using namespace std;
const float epsilon = 0;
//构造方法传递参数
CDynKnapsack::CDynKnapsack(int nNum,float nCapacity,float *nWeight,float *nProfit)
{
n = nNum; //物品数目
m = nCapacity; //背包容量
w = nWeight; //各物品重量
p = nProfit; //各物品效益
}
CDynKnapsack::CDynKnapsack(float *prof,float *wei,float mm,int len)
{
n = len; //物品数目
m = mm; //背包容量
w = wei; //各物品重量
p = prof; //各物品效益
}
//在S(i-1)中求使得point[u].X+w[i]不超过背包载重的最大下标u
int CDynKnapsack::GetMaxValueU(int low,int high,int i)
{
int u = low-1; //赋初值
for(int j=low; j<=high; j++)
{
float ww = point[j].X+w[i];
if(ww <= m) //如果小于等于背包容量则将其下标赋给u
u = j;
}
//返回最大下标u
return u;
}
//从S(0)开始计算所有S(i),并保存point和mark的值及返回最大效益值
float CDynKnapsack::GetOfSandMaxProfit()
{
float ww,pp;
int next; //始终指示数组point中的下一个空的位置
mark[0] = 0; //赋初值
//求S(0)
point[0].X = point[0].P = 0.0;
//point[0].P = 0.0;
point[1].X = w[0];
point[1].P = p[0];
//S(0)的起始位置
int low = 0;
int high = 1;
//next = 2;
mark[1] = next = 2; //数组point的下一个空闲位置
for (int i=1; i<=n-1; i++)
{
int k = low;
//调用GetMaxValueU获取使得point[u].X+w[i]不超过背包载重的最大下标u
int u = GetMaxValueU(low,high,i);
//从S(i-1)生成S(1_i),并合并成S(i)
for(int j=low; j<=u; j++)
{
//生成S(1_i)中的一个阶跃点(ww,pp)
ww = point[j].X+w[i];
pp = point[j].P+p[i];
//复制S(i-1)中的部分阶跃点到s(i)中
while ((k <= high) && (point[k].X < ww))
{
point[next].X = point[k].X;
point[next++].P = point[k++].P;
}
if ((k <= high) && (point[k].X == ww))
if (pp < point[k].P)
pp = point[k++].P;
//若(ww,pp)不被支配,则加入S(i)中
if (pp > point[next-1].P)
{
point[next].X = ww;
point[next++].P = pp;
}
//舍弃所有被支配的阶跃点
while ((k <= high) && (point[k].P <= point[next-1].P))
k++;
}
//复制S(i-1)中剩余的阶跃点到s(i)中
while (k <= high)
{
point[next].X = point[k].X;
point[next++].P = point[k++].P;
}
//S(i+1)初始化
low = high+1;
high = next-1;
mark[i+1] = next;
}
return point[next-1].P; //返回求得的最大效益值
}
//由保存的point和mark回溯求问题的最优解向量
void CDynKnapsack::TraceBack(int *x)
{
//初始化为当前空闲位置的前一个位置
float ww = point[mark[n]-1].X;
//回溯求解向量
for (int j=n-1; j>0; j--)
{
x[j] = 1; //假设(X[n-1],P[n-1])属于S(1_n-1)
//如果(X[n-1],P[n-1])属于S(n-2)则X[n-1]=0
for (int k=mark[j-1]; k<mark[j]; k++)
if (ww == point[k].X)
x[j] = 0;
//如果x[j]==1则减掉w[j]后继续循环
if (x[j])
ww = ww-w[j];
}
//最后一对序偶
if (ww==0)
x[0] = 0;
else
x[0] = 1;
}
void CDynKnapsack::LUBound(float cp,float cw,int k,float &LBB,float &UBB)
{
LBB = cp;
float c = cw;
for (int i=k; i<n; i++)
{
if (c < w[i])
{
UBB = LBB + c*p[i]/w[i];
for (int j=i+1; j<n; j++)
{
if (c >= w[j])
{
c = c-w[j];
LBB = LBB+p[i];
}
}
return;
}
c = c-w[i];
LBB = LBB+p[i];
}
UBB = LBB;
}
float CDynKnapsack::LCBB()
{
Node *child,*E;
float LBB,UBB,L;
ans = NULL;
queue<pqNode> pq;//(N);
root = new Node(NULL,false);
E = root;
LUBound(0,m,0,LBB,UBB);
pqNode e(m,0,UBB,0,root);
L = LBB - epsilon;
do
{
int k = e.level;
float cap = e.cu;
float prof = e.profit;
E = e.ptr;
if ((k == n) && (prof > L))
{
L = prof;
ans = E;
}
else
{
if (cap >= w[k])
{
child = new Node(E,true);
e.ptr = child;
e.level = k+1;
e.cu = cap - w[k];
e.profit = prof + p[k];
pq.push(e);
}
LUBound(prof,cap,k+1,LBB,UBB);
if (UBB > L)
{
child = new Node(E,false);
e.ptr = child;
e.level = k+1;
e.cu = cap;
e.profit = prof;
e.UBB = UBB;
pq.push(e);
if (L < LBB - epsilon)
L = LBB-epsilon;
}
}
if (pq.empty())
return 0;
pq.pop();
}while (e.UBB > L);
return L;
}
用动态规划法求解0/1背包问题
需积分: 15 55 浏览量
2009-04-15
13:08:45
上传
评论 2
收藏 13KB RAR 举报
suyuqin
- 粉丝: 2
- 资源: 13
最新资源
- 基于stm32f103c单片机+MPU6050+0.96英寸OLED显示屏双柄遥控器硬件(原理图+PCB)工程文件.zip
- 整理的关于少儿编程的学习路径,以及如何在小升初,初升高和大学充分的利用起来编程经验的优势
- 足球比赛结果统计表2006-2011年大约28W场比赛
- 基于PHP+mysql的社区交流系统(源代码)
- yolov5,SSD 可能使用到的一些代码
- 一键批量生成多层次文件夹结构,使用Python脚本实现嵌套文件夹批量生成
- 基于c51单片机+DS1302+DHT11温湿度模块+LCD1602显示的万年历硬件原理图+BOM+软件程源码序+仿真图.zip
- NSGA2的MATLAB代码
- Messagepassingtest_GCN_DGL.py
- Sh,Docker 运维好帮手,一招通过 sh 脚本批量快速启动和重启多个Docker 容器
资源上传下载、课程学习等过程中有任何疑问或建议,欢迎提出宝贵意见哦~我们会及时处理!
点击此处反馈