1、贪心法：
有一批集装箱要装上载重量为c的轮船。其中集装箱i的重量为wi，现最优载问题要求确定在装载体积不受限制的情况下，将尽可能多的集装箱装上轮船。
编程任务：对于给定的n个集装箱和轮船的载重量c,编程计算装入的最优装载。
2024-04-14 11:19:34
1.04MB
1
#include
#include
#include
#include
using namespace std;
ifstream infile;
ofstream outfile;
class Node
{
friend int func(int*, int, int, int*);
public:
int ID;
double weight;//物品的重量
};
bool comp1(Node a, Node b) //定义比较规则
{
return a.weight > b.weight;
}
class Load;
class bbnode;
class Current
{
friend Load;
friend struct Comp2;
private:
int upweight;//重量上界
int weight;//结点相应的重量
int level;//活结点在子集树中所处的层次
bbnode* ptr;//指向活结点在子集树中相应结点的指针
};
struct Comp2
{
bool operator () (Current *x, Current *y)
{
return x->upweightupweight;
}
};
class Load
{
friend int func(int*, int, int, int*);
public:
int Max0();
private:
priority_queue, Comp2>H;//利用优先队列（最大堆）储存
int limit(int i);
void AddLiveNode(int up, int cw, bool ch, int level);
bbnode *P;//指向扩展结点的指针
int c;//背包的容量
int n;//物品的数目
int *w;//重量数组
int cw;//当前装载量
int *bestx;//最优解方案数组
};
class bbnode
{
friend Load;
friend int func( int*, int, int, int*);
bbnode* parent;
bool lchild;
}; //结点中有双亲指针以及左儿子标志
int Load::limit(int i) //计算结点所相应重量的上界
{
int left,a;
left= c - cw;//剩余容量
a = cw; //b是重量上界，初始值为已经得到的重量
while (i <= n && w[i] <= left)
{
left -= w[i];
a += w[i];
i++;
}
return a;
}
void Load::AddLiveNode(int up, int cw, bool ch, int level) //将一个新的活结点插入到子集树和优先队列中
{
bbnode *b = new bbnode;
b->parent = P;
b->lchild = ch;
Current* N = new Current;
N->upweight = up;
N->weight = cw;
N->level = level;
N->ptr = b;
H.push(N);
}
int Load::Max0()
{
int i = 1;
P = 0;
cw = 0;
int bestw = 0;
int up = limit(1);
while (i != n + 1)
{
int wt = cw + w[i]; //检查当前扩展结点的左儿子结点
if (wt <= c)//左儿子结点是可行结点
{
if (wt > bestw)
bestw =wt;
AddLiveNode(up,wt, true, i + 1);
}
up = limit(i + 1); //检查当前扩展结点的右儿子结点
if (up >= bestw)//如果右儿子可行
{
AddLiveNode(up,cw, false, i + 1);
}
Current* N = H.top(); //取队头元素
H.pop();
P = N->ptr;
cw = N->weight;
up = N->upweight;
i = N->level;
}
bestx = new int[n + 1];
for (int j = n; j > 0; --j)
{
bestx[j] = P->lchild;
P = P->parent;
}
return cw;
}
int func(int *w, int c, int n, int *bestx) //调用Max0函数对子集树的优先队列式进行分支限界搜索
{
int W = 0; //初始化装载的总质量为0
Node* Q = new Node[n];
for (int i = 0; i < n; ++i)
{
Q[i].ID = i + 1;
Q[i].weight = w[i+1];
W += w[i+1];
}
if (W <= c)//如果足够装，全部装入
return W;
sort(Q, Q + n, comp1); //首先，将各物品按照重量从大到小进行排序；
Load K;
K.w = new int[n + 1];
for (int j = 0; j < n; j++)
K.w[j + 1] = w[Q[j].ID];
K.cw = 0;
K.c = c;
K.n = n;
int bestp = K.Max0();
for (int k = 0; k < n; k++)
{
bestx[Q[k].ID] = K.bestx[k + 1];
}
delete []Q;
delete []K.w;
delete []K.bestx;
return bestp;
}
int main()
{
int*w,*Final;
int c,n,i,best;
infile.open("input.txt",ios::in);
if(!infile)
{
cerr<<"open error"<>c;
infile>>n;
w=new int[n+1];
for(i=1;i<=n;i++)
infile>>w[i];
infile.close();
Final = new int[n+1];
best = func( w, c, n, Final);
outfile.open("output.txt",ios::out);
if(!outfile)
{
cerr<<"open error"<
2022-06-07 18:10:13
4KB
1
一、 实验目的
1、理解回溯法的深度优先搜索策略。
2、掌握用回溯法解题的算法框架。
3、通过应用范例学习回溯法的设计策略。
二、实验环境
1、硬件环境：Windows 10
2、软件环境：
编译器：Dev C++
语言：C语言
2022-06-06 19:09:25
236KB
1
有一批集装箱要装上一艘载重量为C的轮船。其中集装箱i的重量为wi。最优装载问题要求确定在装载体积不受限制的情况下，将尽可能多的集装箱装上轮船。
Input
输入的第一个为测试样例的个数T（ T <= 100 ），接下来有T个测试样例。每个测试样例的第一行是一个整数n（ n <= 1000 ）和一个非负数C（ C <= 10000 ），分别表示集装箱的个数以及轮船的载重量。接下来有n行，每行一个非负数，表示每个集装箱的重量。
2022-05-18 14:57:32
6KB
1