URAL 1005. Stone Pile
Contents [show]
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 3Problem 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; } } } }