URAL 1005. Stone Pile

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;
}
}
}
}
#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; } } } }
#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;
            }
        }
    }
}