算法(九)-回溯法-装载问题

问题描述：

算法思想：

代码实现：

#include <iostream>
using namespace std;

class Loading
{
public:
    void getBest();

private:
    void backTrack(int);
    void init();

private:
    int n;//集装箱个数
    int *w;//集装箱重量组数
    int c;//第一艘轮船的载重量
    int cw;//当前载重量
    int best;//当前最优重量
};

void Loading::getBest()
{
    init();
    backTrack(1);
    cout<<"the best = "<<best<<endl;
    delete[] w;
}

void Loading::init()
{
    cout<<"Please input n: ";
    cin >> n;
    cout<<"Please input the weight of the first ship: ";
    cin>>c;
    cout<<"Please input the weight of every packet: ";
    w = new int[n+1];
    w[0] = 0;
    for(int i = 1; i <= n; i++)
        cin>>w[i];

    cw = 0;
    best = 0;
}

void Loading::backTrack(int i)
{
    if(i > n)
    {
        if(cw > best)
            best = cw;
        return;
    }
    if(cw + w[i] <= c)
    {
        cw += w[i];
        backTrack(i+1);
        cw -= w[i];
    }
    backTrack(i+1);
}

int main()
{
    Loading loading = Loading();
    loading.getBest();
    system("pause");
    return 0;
}