Problem C: Cat
In strong winds, sailboats tend to heel leeward (tilt away from the
wind) like the one in the picture. Heeling is undesirable for at
least two reasons. First, the effective sail area is reduced, as the effective
height of the sail is multiplied by the cosine of the angle. Reduced sail
area implies reduced speed. Second, the boat may heel to the point that
its centre of gravity ceases to be above the hull, causing the boat to
capsize.
To mitigate these problems, catamarans like the one shown split the hull
into two pieces (the port and starboard hulls). This design increases the
effective width of the boat. Increased width
decreases the vertical mechanical advantage
of the sail, thus reducing heeling. Increased width
also increases the angle of heeling that can be tolerated before
the boat capsizes.
Heeling can also be mitigated by having the crew sit or stand, or even
hike out beyond, the windward hull. If you look carefully at the picture
you can see the two person crew hiking to windward.
At some wind velocity, even these measures are insufficient to keep the boat
upright. A skipper's only choice (other than to capsize) is to let out
the sail, which reduces its effective horizontal dimension much as heeling
reduces its vertical dimension. As with heeling, this action causes loss
of speed. If the boat heels sufficiently, it may not even be possible to
let out the sail, as is outer corner may be obstructed by the surface
of the water!
Reefing is a mechanism for reducing the sail's area. Roller reefing involves
wrapping the sail around the boom (much like a window blind) so as to
reduce its height. With sufficient reefing, the heeling can be controlled
in almost any wind.
But reefing involves reduced speed, so our skipper has elected yet another
approach. She has decided to beach the boat and pick up some rocks to
use as ballast. Ballast is just dead weight added to hull, which tends
to counteract heeling. It slows the boat a bit
(as it rides lower in the water) but not nearly so much as reducing
sail area.
Given n rocks, you are to compute how to divide them between the
port and starboard hulls so that the weight of rocks in each hull is
nearly equal.
Input contains several test cases. Each test case begins with 1 <
n <= 100; the number of rocks to be added as ballast.
Consider the rocks to be numbered 1 through n. n lines
follow; the ith line gives the weight in kg of the ith rock - a
positive real number not greater than 100. A line containing 0 follows the last
test case.
For each test case, output a single line giving the numbers of the rocks
that should be loaded as ballast into the starboard hull. Assume that
the other rocks will be loaded into the port hull. The total weight of
ballast in the port hull should not differ from that in the starboard
hull by more than 2%. If there are many solutions, any one will do.
There will always be a solution; indeed, there will always be a solution
that balances within 1%, but you aren't required to find it.
Sample Input
5
10.0
50.0
90.0
38.0
7.1
0
Possible Output for Sample Input
3 5
Gordon V. Cormack
題目描述：
分成兩堆重量差異最小的，並且輸出其中較輕的一堆。
題目解法：
原本是想要用基因算法，但寫到後面，發現隨機 1000 組就過了。
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <algorithm>
using namespace std;
struct Gene {
int DNA[4], n;
double h;
Gene() {
memset(DNA, 0, sizeof(DNA));
}
int GET(int x) {
return DNA[x>>5]>>((x)&31)&1;
}
void SET(int x) {
DNA[x>>5] |= 1<<((x)&31);
}
void NSET(int x) {
DNA[x>>5] ^= 1<<((x)&31);
}
Gene crossover(Gene y) {
int p = rand()%n;
for(int i = p; i < n; i++) {
int a = GET(i), b = y.GET(i);
if(a != b) {
y.NSET(i);
}
}
return y;
}
void mutation() {
int p = rand()%n;
NSET(p);
}
double fitness(double w[], double k) {
double c = -k;
for(int i = 0; i < n; i++) {
if(GET(i))
c += w[i];
}
if(c < 0) c = -c;
h = c = 1 - c/k;
return h;
}
};
bool cmp(Gene a, Gene b) {
return a.h < b.h;
}
double randDouble() {
return (rand() % 32767) / 32767.0;
}
void Genetic_Algorithm(int n, double w[]) {
#define ITERATE 15
#define CREATURE 505
Gene Pool[CREATURE], NPool[CREATURE];
double half = 0;
for(int i = 0; i < n; i++)
half += w[i];
half /= 2.0;
// init
for(int i = 0; i < CREATURE; i++) {
for(int j = 0; j < n; j++) {
int k = rand()%2;
if(k) Pool[i].SET(j);
}
Pool[i].n = n;
Pool[i].fitness(w, half);
}
sort(Pool, Pool + CREATURE, cmp);
Gene bestGene = Pool[CREATURE-1];
//
double board[CREATURE], tot;
for(int i = 0; i < ITERATE; i++) {
tot = 0;
for(int j = 0; j < CREATURE; j++) {
tot += Pool[j].h;
}
board[0] = Pool[0].h / tot;
for(int j = 1; j < CREATURE; j++) {
board[j] = board[j-1] + Pool[j].h / tot;
}
for(int j = 0; j < CREATURE; j++) {
int x = lower_bound(board, board + CREATURE, randDouble()) - board;
int y = lower_bound(board, board + CREATURE, randDouble()) - board;
NPool[j] = Pool[x].crossover(Pool[y]);
}
for(int j = 0; j < CREATURE; j++) {
Pool[j] = NPool[j];
Pool[j].mutation();
Pool[j].n = n;
Pool[j].fitness(w, half);
}
sort(Pool, Pool + CREATURE, cmp);
if(Pool[CREATURE-1].h < bestGene.h)
bestGene = Pool[CREATURE-1];
}
double out = 0;
for(int i = 0; i < n; i++) {
if(bestGene.GET(i))
out += w[i];
}
int f = 0;
for(int i = 0; i < n; i++) {
if(out < half) {
if(bestGene.GET(i)) {
if(f) putchar(' ');
f = 1;
printf("%d", i+1);
}
} else {
if(!bestGene.GET(i)) {
if(f) putchar(' ');
f = 1;
printf("%d", i+1);
}
}
}
puts("");
}
int main() {
int n;
double w[105];
while(scanf("%d", &n) == 1 && n) {
for(int i = 0; i < n; i++) {
scanf("%lf", &w[i]);
}
Genetic_Algorithm(n, w);
}
return 0;
}
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <algorithm>
using namespace std;
struct Gene {
int DNA[4], n;
double h;
Gene() {
memset(DNA, 0, sizeof(DNA));
}
int GET(int x) {
return DNA[x>>5]>>((x)&31)&1;
}
void SET(int x) {
DNA[x>>5] |= 1<<((x)&31);
}
void NSET(int x) {
DNA[x>>5] ^= 1<<((x)&31);
}
Gene crossover(Gene y) {
int p = rand()%n;
for(int i = p; i < n; i++) {
int a = GET(i), b = y.GET(i);
if(a != b) {
y.NSET(i);
}
}
return y;
}
void mutation() {
int p = rand()%n;
NSET(p);
}
double fitness(double w[], double k) {
double c = -k;
for(int i = 0; i < n; i++) {
if(GET(i))
c += w[i];
}
if(c < 0) c = -c;
h = c = 1 - c/k;
return h;
}
};
bool cmp(Gene a, Gene b) {
return a.h < b.h;
}
double randDouble() {
return (rand() % 32767) / 32767.0;
}
void Genetic_Algorithm(int n, double w[]) {
#define ITERATE 16
#define CREATURE 600
Gene Pool[CREATURE], NPool[CREATURE];
double half = 0;
for(int i = 0; i < n; i++)
half += w[i];
half /= 2.0;
// init
for(int i = 0; i < CREATURE; i++) {
for(int j = 0; j < n; j++) {
int k = rand()%2;
if(k) Pool[i].SET(j);
}
Pool[i].n = n;
Pool[i].fitness(w, half);
}
sort(Pool, Pool + CREATURE, cmp);
Gene bestGene = Pool[CREATURE-1];
//
double board[CREATURE], tot;
for(int i = 0; i < ITERATE; i++) {
tot = 0;
for(int j = 0; j < CREATURE; j++) {
tot += Pool[j].h;
}
board[0] = Pool[0].h / tot;
for(int j = 1; j < CREATURE; j++) {
board[j] = board[j-1] + Pool[j].h / tot;
}
for(int j = 0; j < CREATURE; j++) {
int x = lower_bound(board, board + CREATURE, randDouble()) - board;
int y = lower_bound(board, board + CREATURE, randDouble()) - board;
NPool[j] = Pool[x].crossover(Pool[y]);
}
for(int j = 0; j < CREATURE; j++) {
Pool[j] = NPool[j];
if(randDouble() < 0.2)
Pool[j].mutation();
Pool[j].n = n;
Pool[j].fitness(w, half);
}
sort(Pool, Pool + CREATURE, cmp);
if(Pool[CREATURE-1].h < bestGene.h)
bestGene = Pool[CREATURE-1];
}
double out = 0;
for(int i = 0; i < n; i++) {
if(bestGene.GET(i))
out += w[i];
}
int f = 0;
for(int i = 0; i < n; i++) {
if(out < half) {
if(bestGene.GET(i)) {
if(f) putchar(' ');
f = 1;
printf("%d", i+1);
}
} else {
if(!bestGene.GET(i)) {
if(f) putchar(' ');
f = 1;
printf("%d", i+1);
}
}
}
puts("");
}
int main() {
int n;
double w[105];
while(scanf("%d", &n) == 1 && n) {
for(int i = 0; i < n; i++) {
scanf("%lf", &w[i]);
}
Genetic_Algorithm(n, w);
}
return 0;
}
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <algorithm>
using namespace std;
struct Gene {
int DNA[4], n;
double h;
Gene() {
memset(DNA, 0, sizeof(DNA));
}
int GET(int x) {
return DNA[x>>5]>>((x)&31)&1;
}
void SET(int x) {
DNA[x>>5] |= 1<<((x)&31);
}
void NSET(int x) {
DNA[x>>5] ^= 1<<((x)&31);
}
Gene crossover(Gene y) {
int p = rand()%n;
for(int i = p; i < n; i++) {
int a = GET(i), b = y.GET(i);
if(a != b) {
y.NSET(i);
}
}
return y;
}
void mutation() {
int p = rand()%n;
NSET(p);
}
double fitness(double w[], double k) {
double c = -k;
for(int i = 0; i < n; i++) {
if(GET(i))
c += w[i];
}
if(c < 0) c = -c;
h = c = 1 - c/k;
return h;
}
};
bool cmp(Gene a, Gene b) {
return a.h < b.h;
}
double randDouble() {
return (rand() % 32767) / 32767.0;
}
void Genetic_Algorithm(int n, double w[]) {
#define ITERATE 1
#define CREATURE 1000
Gene Pool[CREATURE], NPool[CREATURE];
double half = 0;
for(int i = 0; i < n; i++)
half += w[i];
half /= 2.0;
// init
for(int i = 0; i < CREATURE; i++) {
for(int j = 0; j < n; j++) {
int k = rand()%2;
if(k) Pool[i].SET(j);
}
Pool[i].n = n;
Pool[i].fitness(w, half);
}
sort(Pool, Pool + CREATURE, cmp);
Gene bestGene = Pool[CREATURE-1];
//
double board[CREATURE], tot;
for(int i = 0; i < ITERATE; i++) {
tot = 0;
for(int j = 0; j < CREATURE; j++) {
tot += Pool[j].h;
}
board[0] = Pool[0].h / tot;
for(int j = 1; j < CREATURE; j++) {
board[j] = board[j-1] + Pool[j].h / tot;
}
for(int j = 0; j < CREATURE; j++) {
int x = lower_bound(board, board + CREATURE, randDouble()) - board;
int y = lower_bound(board, board + CREATURE, randDouble()) - board;
NPool[j] = Pool[x].crossover(Pool[y]);
}
for(int j = 0; j < CREATURE; j++) {
Pool[j] = NPool[j];
if(randDouble() < 0.2)
Pool[j].mutation();
Pool[j].n = n;
Pool[j].fitness(w, half);
}
sort(Pool, Pool + CREATURE, cmp);
if(Pool[CREATURE-1].h < bestGene.h)
bestGene = Pool[CREATURE-1];
}
double out = 0;
for(int i = 0; i < n; i++) {
if(bestGene.GET(i))
out += w[i];
}
int f = 0;
for(int i = 0; i < n; i++) {
if(out < half) {
if(bestGene.GET(i)) {
if(f) putchar(' ');
f = 1;
printf("%d", i+1);
}
} else {
if(!bestGene.GET(i)) {
if(f) putchar(' ');
f = 1;
printf("%d", i+1);
}
}
}
puts("");
}
int main() {
int n;
double w[105];
while(scanf("%d", &n) == 1 && n) {
for(int i = 0; i < n; i++) {
scanf("%lf", &w[i]);
}
Genetic_Algorithm(n, w);
}
return 0;
}
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <algorithm>
using namespace std;
struct Gene {
int DNA[4], n;
double h;
Gene() {
memset(DNA, 0, sizeof(DNA));
}
int GET(int x) {
return DNA[x>>5]>>((x)&31)&1;
}
void SET(int x) {
DNA[x>>5] |= 1<<((x)&31);
}
void NSET(int x) {
DNA[x>>5] ^= 1<<((x)&31);
}
Gene crossover(Gene y) {
int p = rand()%n;
for(int i = p; i < n; i++) {
int a = GET(i), b = y.GET(i);
if(a != b) {
y.NSET(i);
}
}
return y;
}
void mutation() {
int p = rand()%n;
NSET(p);
}
double fitness(double w[], double k) {
double c = -k;
for(int i = 0; i < n; i++) {
if(GET(i))
c += w[i];
}
if(c < 0) c = -c;
h = c = 1 - c/k;
return h;
}
};
bool cmp(Gene a, Gene b) {
return a.h < b.h;
}
double randDouble() {
return (rand() % 32767) / 32767.0;
}
void Genetic_Algorithm(int n, double w[]) {
#define ITERATE 0
#define CREATURE 750
Gene Pool[CREATURE], NPool[CREATURE];
double half = 0;
for(int i = 0; i < n; i++)
half += w[i];
half /= 2.0;
// init
for(int i = 0; i < CREATURE; i++) {
for(int j = 0; j < n; j++) {
int k = rand()%2;
if(k) Pool[i].SET(j);
}
Pool[i].n = n;
Pool[i].fitness(w, half);
}
sort(Pool, Pool + CREATURE, cmp);
Gene bestGene = Pool[CREATURE-1];
//
double board[CREATURE], tot;
for(int i = 0; i < ITERATE; i++) {
tot = 0;
for(int j = 0; j < CREATURE; j++) {
tot += Pool[j].h;
}
board[0] = Pool[0].h / tot;
for(int j = 1; j < CREATURE; j++) {
board[j] = board[j-1] + Pool[j].h / tot;
}
for(int j = 0; j < CREATURE; j++) {
int x = lower_bound(board, board + CREATURE, randDouble()) - board;
int y = lower_bound(board, board + CREATURE, randDouble()) - board;
NPool[j] = Pool[x].crossover(Pool[y]);
}
for(int j = 0; j < CREATURE; j++) {
Pool[j] = NPool[j];
if(randDouble() < 0.2)
Pool[j].mutation();
Pool[j].n = n;
Pool[j].fitness(w, half);
}
sort(Pool, Pool + CREATURE, cmp);
if(Pool[CREATURE-1].h < bestGene.h)
bestGene = Pool[CREATURE-1];
}
double out = 0;
for(int i = 0; i < n; i++) {
if(bestGene.GET(i))
out += w[i];
}
int f = 0;
for(int i = 0; i < n; i++) {
if(out < half) {
if(bestGene.GET(i)) {
if(f) putchar(' ');
f = 1;
printf("%d", i+1);
}
} else {
if(!bestGene.GET(i)) {
if(f) putchar(' ');
f = 1;
printf("%d", i+1);
}
}
}
puts("");
}
int main() {
int n;
double w[105];
while(scanf("%d", &n) == 1 && n) {
for(int i = 0; i < n; i++) {
scanf("%lf", &w[i]);
}
Genetic_Algorithm(n, w);
}
return 0;
}
文章定位：
