装载问题-回溯法

问题描述:

  有一批共n个集装箱要装上2艘载重量分别为c1和c2的轮船,其中集装箱i的重量是wi,且不能超。

算法思想:

  最优装载方案: 将第一艘轮船尽可能的装满;  然后将剩余的装载第二艘船上

算法描述:

template <class Type>
class Loading
{
    friend Type MaxLoading(Type [],Type,int);
    private:
        void Backtrack(int i);
        int n;
        Type * w,c,cw,bestw;
};
template <class Type>
void Loading<Type>::Backtrack(int i)
{
    if(i>n)
    {
        if(cw>bestw)
            bestw = cw;
        return;
    }
    if(cw+w[i] <= c)
    {
        cw += w[i];
        Backtrack(i+1);
        cw -= w[i];
    }
    Backtrack(i+1);
}
template <class Type>
Type MaxLoading(Type w[],Type c,int n)
{
    Loading<Type> X;
    X.w = w;
    X.c = c;
    X.n = n;
    X.bestw = 0;
    X.cw = 0;
    X.Backtrack(1);
    return X.bestw;
}

上界函数:

引入上界函数,用于剪去不含最优解的子树:

template <class Type>
class Loading
{
    friend Type MaxLoading(Type [],Type,int);
    private:
        void Backtrack(int i);
        int n;
        Type * w,
            c,
            cw,
            bestw,
            r;//剩余集装箱重量
};
template <class Type>
void Loading<Type>::Backtrack(int i)
{
    if(i>n)
    {
        if(cw>bestw)
            bestw = cw;
        return;
    }
    r-=w[i];//计算剩余的集装箱的重量
    if(cw+w[i] <= c)
    {
        cw += w[i];
        Backtrack(i+1);
        cw -= w[i];
    }
    Backtrack(i+1);
    r+=w[i];//如果得不到最优解,再取消当前的集装箱,表示未选,因此剩余容量要再加上当前集装箱重量
}
template <class Type>
Type MaxLoading(Type w[],Type c,int n)
{
    Loading<Type> X;
    X.w = w;
    X.c = c;
    X.n = n;
    X.bestw = 0;
    X.cw = 0;
    X.r = 0;
    for(int i=1;i<=n;i++)//计算总共的剩余集装箱重量
        X.r += w[i];
    X.Backtrack(1);
    return X.bestw;
}

构造最优解:

   为了构造最优解,必须在算法中保存最优解的记录。因此需要两个成员数组 x ,bestx,一个用于记录当前的选择,一个用于记录最优记录。

改进后的算法描述如下:

template <class Type>
class Loading
{
    friend Type MaxLoading(Type [],Type,int);
    private:
        void Backtrack(int i);
        int n,
            * x,
            * bestx;
        Type * w,
            c,
            cw,
            bestw,
            r;//剩余集装箱重量
};
template <class Type>
void Loading<Type>::Backtrack(int i)
{
    if(i>n)
    {
        if(cw>bestw)
        {
            for(j=1;j<=n;j++)
                bestx[j] = x[j];
            bestw = cw;
        }
        return;
    }
    r-=w[i];//计算剩余的集装箱的重量
    if(cw+w[i] <= c)
    {
        x[i] =1;
        cw += w[i];
        Backtrack(i+1);
        cw -= w[i];
    }
    if(cw+r > bestw)
    {
        x[i] = 0;
        Backtrack(i+1);
    }
    r+=w[i];//如果得不到最优解,再取消当前的集装箱,表示未选,因此剩余容量要再加上当前集装箱重量
}
template <class Type>
Type MaxLoading(Type w[],Type c,int n)
{
    Loading<Type> X;
    X.w = w;
    X.c = c;
    X.n = n;
    X.bestx = bestx;
    X.bestw = 0;
    X.cw = 0;
    X.r = 0;
    for(int i=1;i<=n;i++)//计算总共的剩余集装箱重量
        X.r += w[i];
    X.Backtrack(1);
    delete []X,x;
    return X.bestw;
}

迭代回溯方式:

利用数组x所含的信息,可将上面方法表示成非递归的形式。省去O(n)递归栈空间。

template <class Type>
Type MaxLoading(Type w[],Type c,int n,int bestx[])
{
    //迭代回溯法,返回最优装载量及其相应解,初始化根节点
    int i =1;
    int *x = new int[n+1];
    Type bestw = 0,
        cw = 0,
        r = 0;
    for(int j=1;j<=n;j++)
        r+=w[j];
    while(true)
    {
        while(i<=n && cw+w[i]<=c)
        {
            r -= w[i];
            cw +=w[i];
            x[i] =1;
            i++;
        }
        if(i>n)
        {
            for(int j=1;j<=n;j++)
                bestx[j] = x[j];
            bestw = cw;
        }
        else
        {
            r -= w[i];
            x[i] = 0;
            i++;
        }
        while(cw+w[i] <= bestw)
        {
            i--;
            while(i>0 && !x[i])
            {
                r+=w[i];
                i--;
            }
            if(i == 0)
            {
                delete[] x;
                return bestw;
            }
            x[i] =0;
            cw -= w[i];
            i++;
        }
    }
}

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏我有一个梦想

Python 项目实践二(下载数据)第三篇

接着上节继续学习,在本章中,你将从网上下载数据,并对这些数据进行可视化。网上的数据多得难以置信,且大多未经过仔细检查。如果能够对这些数据进行分析,你就能发现别人...

2865
来自专栏听雨堂

Pandas对行情数据的预处理

库里是过去抓取的行情数据,间隔6秒,每分钟8-10个数据不等,还有开盘前后的一些数据,用Pandas可以更加优雅地进行处理。 ? 需要把当前时间设置为index...

22110
来自专栏XAI

Java分布式神经网络库Deeplearning4j之上手实践手写数字图像识别与模型训练

环境的搭建可以参考另一篇文章。 Java分布式神经网络库Deeplearning4j 环境搭建和运行一个例子 代码所在包截图示意 ? 第一步运行MnistIm...

1K10
来自专栏我的小碗汤

19个很有用的 ElasticSearch 查询语句 篇二

另一个结构化查询的例子是 范围查询。在这个例子中,我们要查找 2015 年出版的书。

1.3K3
来自专栏落影的专栏

GPUImage详细解析

从源码的角度分析、学习GPUImage和OpenGL ES,这是第一篇,介绍GPUImageFilter 和 GPUImageFramebuffer。 Open...

3466
来自专栏章鱼的慢慢技术路

层层递进——宽度优先搜索(BFS)

2414
来自专栏尾尾部落

[剑指offer] 顺时针打印矩阵

输入一个矩阵,按照从外向里以顺时针的顺序依次打印出每一个数字,例如,如果输入如下矩阵: 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 ...

2132
来自专栏有趣的Python和你

Python数据分析之pandas数据可视化折线图条形图pandas绘图乱码解决

2304
来自专栏机器学习原理

深度学习(2)——tensorflow可视化TensorFlow变量作用域TensorFlow可视化示例

1625
来自专栏专知

【干货】使用TensorFlow官方Java API调用TensorFlow模型(附代码)

1.7K4

扫码关注云+社区

领取腾讯云代金券