练习题 - 石子合并(动态规划)

前言

算法拾遗继续。

题目

你有一堆石头质量分别为 W1,W2,W3...WN.(W<=100000) 现在需要你将石头合并为两堆,使两堆质量的差的绝对值为最小。

输入:

第一行为整数N(1<=N<=20),表示有N堆石子。
第二行:是n个数,为每堆石子的质量。

输出:

一行。只需输出合并后两堆的质量差的绝对值的最小值

样例: 输入:

5
5 8 13 27 14

输出:

3

解答

这个问题可以转化为求数组的一个子集,使得这个子集中的元素的和尽可能接近sum/2,其中sum为数组中所有元素的和。

这样转换之后这个问题就很类似0-1背包问题了:在n件物品中找到m件物品,他们的可以装入背包中,且总价值最大不过这里不考虑价值,就考虑使得这些元素的和尽量接近sum/2。

#include <stdio.h>

FILE *in, *out;
int n, w[100001]={0}, sum=0, mid, min=2100000000;

void swap(int i,int j) {
    int tem;
    tem = w[i];
    w[i] = w[j];
    w[j] = tem;
}

void search(int k, int tot) {
    if(mid - tot == 0) {
        if(sum == mid * 2)
            fprintf(out, "%d\n", 0);
        else 
            fprintf(out, "%d\n", 1);
        exit(0);
    }

    if(mid - tot > 0 && mid - tot < min)
        min = mid - tot;

    if(tot > mid)
        return;
    if(k > n)
        return;

    int i;
    for(i = 0; i <= 1; i++)
       search(k + 1, tot + w[k] * i);
}

int main() {
    in=fopen("A.in", "r");
    fscanf(in, "%d", &n);

    int i;
    for(i = 1; i <= n; i++) {
        fscanf(in, "%d", &w[i]);
        sum += w[i];
    }
    fclose(in);

    mid = sum / 2;
    int j;
    for(i = 1; i < n; i++)
        for(j = i + 1; j <= n; j++)
          if(w[i] > w[j])
              swap(i, j);

    serch(1, 0);

    // printf("%d %d\n", 2 * min, sum); getchar();

    out = fopen("A.out", "w");
    if(sum == mid * 2)
        fprintf(out, "%d\n", 2 * min);
    else 
        fprintf(out, "%d\n", 2 * min + 1);
    /*
    if(min != mid)
        fprintf(out, "%d", sum - 2 * min);
    else 
        fprintf(out, "%d", sum);
   */
    fclose(out);

    return 0;
}

参考


* cached version, generated at 2018-12-02 16:10:20 UTC.

Subscribe by RSS