URAL 1005. Stone Pile

Author: 2015-08-22

ACM

, ,

1. 题目

http://acm.timus.ru/problem.aspx?space=1&num=1005

1005. Stone Pile

Time limit: 1.0 second
Memory limit: 64 MB
You have a number of stones with known weights w1, …, wn. Write a program that will rearrange the stones into two piles such that weight difference between the piles is minimal.

Input

Input contains the number of stones n (1 ≤ n ≤ 20) and weights of the stones w1, …, wn (integers, 1 ≤ wi ≤ 100000) delimited by white spaces.

Output

Your program should output a number representing the minimal possible weight difference between stone piles.

Sample

input output 
5
5 8 13 27 14

3
Problem Source: USU Championship 1997

2. 思路

n块石头分成两堆，求两堆石头的重量差的最小值。

n最大只有20，可以暴力破解。下面的代码使用01背包求解。

3. 代码

#include <stdio.h>
#include <string.h>

#define MAX_STONE_NUM 20
#define MAX_PILE_WEIGHT 100000
#define PACK_SIZE MAX_PILE_WEIGHT * MAX_STONE_NUM

void solveE2d();
int inputPiles(int piles[], int n);
void buildPack(int pack[], int capacity, int piles[], int n);

int main() {
    solveE2d();
    return 0;
}

int pack[PACK_SIZE];
void solveE2d() {
    int n, piles[MAX_STONE_NUM], totalWeight, result;

    scanf("%d", &n);
    totalWeight = inputPiles(piles, n);
    buildPack(pack, totalWeight / 2, piles, n);
    result = totalWeight - pack[totalWeight / 2] * 2;
    printf("%d\n", result);
}

int inputPiles(int piles[], int n) {
    int i, totalWeight;

    for (i = 0, totalWeight = 0; i < n; ++i) {
        scanf("%d", &piles[i]);
        totalWeight += piles[i];
    }
    return totalWeight;
}

void buildPack(int pack[], int capacity, int piles[], int n) {
    int i, j, weightWithPileI;
    
    memset(pack, 0, sizeof(int) * PACK_SIZE);

    for (i = 0; i < n; ++i) {
        for (j = capacity; j >= piles[i]; --j) {
            weightWithPileI = pack[j - piles[i]] + piles[i];
            if (weightWithPileI > pack[j]) {
                pack[j] = weightWithPileI;
            }
        }
    }
}