You cannot select more than 25 topics
Topics must start with a letter or number, can include dashes ('-') and can be up to 35 characters long.
95 lines
2.4 KiB
C
95 lines
2.4 KiB
C
#include <stdio.h>
|
|
#include <stdlib.h>
|
|
#include <stdint.h>
|
|
|
|
typedef struct
|
|
{
|
|
const char * name;
|
|
int weight, value;
|
|
} item_t;
|
|
|
|
item_t item[] =
|
|
{
|
|
{"map", 9, 150},
|
|
{"compass", 13, 35},
|
|
{"water", 153, 200},
|
|
{"sandwich", 50, 160},
|
|
{"glucose", 15, 60},
|
|
{"tin", 68, 45},
|
|
{"banana", 27, 60},
|
|
{"apple", 39, 40},
|
|
{"cheese", 23, 30},
|
|
{"beer", 52, 10},
|
|
{"suntancream", 11, 70},
|
|
{"camera", 32, 30},
|
|
{"T-shirt", 24, 15},
|
|
{"trousers", 48, 10},
|
|
{"umbrella", 73, 40},
|
|
{"waterproof trousers", 42, 70},
|
|
{"waterproof overclothes", 43, 75},
|
|
{"note-case", 22, 80},
|
|
{"sunglasses", 7, 20},
|
|
{"towel", 18, 12},
|
|
{"socks", 4, 50},
|
|
{"book", 30, 10}
|
|
};
|
|
|
|
#define n_items (sizeof(item)/sizeof(item_t))
|
|
|
|
typedef struct
|
|
{
|
|
uint32_t bits; /* 32 bits, can solve up to 32 items */
|
|
int value;
|
|
} solution;
|
|
|
|
void optimal(int weight, int idx, solution *s)
|
|
{
|
|
solution v1, v2;
|
|
if (idx < 0)
|
|
{
|
|
s->bits = s->value = 0;
|
|
return;
|
|
}
|
|
if (weight < item[idx].weight)
|
|
{
|
|
optimal(weight, idx - 1, s);
|
|
return;
|
|
}
|
|
optimal(weight, idx - 1, &v1);
|
|
optimal(weight - item[idx].weight, idx - 1, &v2);
|
|
v2.value += item[idx].value;
|
|
v2.bits |= (1 << idx);
|
|
*s = (v1.value >= v2.value) ? v1 : v2;
|
|
}
|
|
|
|
int main(void)
|
|
{
|
|
int i = 0, w = 0;
|
|
solution s = {0, 0};
|
|
optimal(400, n_items - 1, &s);
|
|
for (i = 0; i < n_items; i++)
|
|
{
|
|
if (s.bits & (1 << i))
|
|
{
|
|
printf("%s\n", item[i].name);
|
|
w += item[i].weight;
|
|
}
|
|
}
|
|
printf("Total value: %d; weight: %d\n", s.value, w);
|
|
return 0;
|
|
}
|
|
|
|
/*
|
|
map
|
|
compass
|
|
water
|
|
sandwich
|
|
glucose
|
|
banana
|
|
suntancream
|
|
waterproof trousers
|
|
waterproof overclothes
|
|
note-case
|
|
sunglasses
|
|
socks
|
|
Total value: 1030; weight: 396
|