多元Huffman编码变形—回溯法

• 2020 年 11 月 27 日
• 笔记
• C++, 算法不能丢, 算法基础

一、问题描述

描述

在一个操场的四周摆放着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

136

问题分析

• 首先用分支界限法（回溯法）找出每次合并石子堆数和可用次数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;
}