一、问题描述

描述

在一个操场的四周摆放着n堆石子。现要将石子有次序地合并成一堆。规定在合并过程中最多可以有m(k)次选k堆石子合并成新的一堆，2≤k≤n，合并的费用为新的一堆的石子数。试设计一个算法，计算出将n堆石子合并成一堆的最小总费用。对于给定n堆石子,计算合并成一堆的最小总费用。

输入

输入数据的第1 行有1 个正整数n（n≤100），表示有n 堆石子。第2行有n个数，分别表示每堆石子的个数。第3 行有n-1 个数，分别表示m(k)（2≤k≤n）的值。

输出Output

将计算出的最小总费用输出。问题无解时输出“No solution!”

Sample Input

7

45 13 12 16 9 5 22

3 3 0 2 1 0

Sample Output

问题分析

首先用分支界限法（回溯法）找出每次合并石子堆数和可用次数v[i]
然后对石子从小到大排序，每次取最小堆数合并石子（这样保证越往后合并的堆数就越多）
这样就就可以保证最小输出

代码

#include<iostream>

#include<algorithm>

using namespace std;

int n;

int p[201];

int m[101];

int v[101];

/**

分支界限法 找出每次合并石子堆数和可用次数

参数：第i次合并，还剩余sum堆石子

*/

bool branch(int i,int sum){

    if(i==1){

        if(sum==1)

            return true;

        else

            return false;

    }

    for(int j=m[i];j>=0;j--){

        v[i] = j;

        if(sum-v[i]*(i-1)<=0){

            continue;

        }

        if(branch(i-1,sum-v[i]*(i-1))){

            return true;

        }

    }

    return false;

}

/**

把数组P中的第n-1个数据，插入到i到n-2数据里，

相当于把i到n从小到大排序

*/

void my_sorted(int i){

    for (int j = n-1; j >= i; --j) {

        if(p[j]<p[j-1]){

            swap(p[j],p[j-1]);

        }

        else

            break;

    }

}

int main(){

    cin>>n;

    for (int i = 0; i < n; ++i) {

        cin>>p[i];

    }

    for (int i = 2; i <= n; ++i) {

        cin>>m[i];

    }

    //判断是否有解，并且把每次需要合并多少堆石子求出来

    if(!branch(n,n)){

        cout<<"No solution!"<<endl;

        return 0;

    }

    sort(p,p+n);

//        for(int i=0;i<=n;i++){

//            cout<<v[i]<<' ';

//        }

//        cout<<endl;

    int min = 0;

    int start = 0;

    int num = n;

    for (int i = 1; i <= num;i++) {

        for(int k = 0;k < v[i];k++){

            int min2 = 0;

            for (int j = 0; j < i; ++j) {

                min2 += p[start++];

            }

            p[n++] = min2;

            min += min2;

            my_sorted(start);

        }

    }

    cout<<min<<endl;

}

巴特西

多元Huffman编码变形—回溯法

一、问题描述

描述

输入

输出Output

Sample Input

Sample Output

问题分析

代码

最新文章

热门文章