#include <stdio.h>
//structure.
struct Item {
long int value;
long int weight;
double efficiency;
};
//functions.
void quick_sort(int array[], int left, int right); //QuickSort.
long int getUpperBound(int i, long int w); //i番目以降、要領wの上界.
long int searchMax(int i, long int w, long int sum, int rec_size, int record[]); //i番目以降、要領wの最大値.
//variables.
int N;
long int W;
struct Item *items;
int *efficiency_sort;
long int MAX = 0;
int *record_max;
int record_size = 0;
int main(int argc, char *argv[]){
//scan input.
printf("Scanning input file\n");
FILE *file;
file = fopen(argv[1], "r");
if(file == NULL) {
printf("It is impossible to read %s!\n", argv[1]);
return -1;
}
fscanf(file, "%d %ld", &N, &W);
struct Item item_array[N]; items = item_array;
for (int i = 0; i < N; i++) {
long int v,w;
fscanf(file, "%ld %ld", &v, &w);
double e = ((double) v)/((double)w);
struct Item item = {v, w, e};
item_array[i] = item;
}
//print input.
printf("N=%d W=%ld\n", N, W);
for (int i = 0;i < N;i++) {
struct Item *item = items + i;
printf("%d: %ld %ld %lf\n", i, item->value, item->weight, item->efficiency);
}
//sort.
printf("Sorting\n");
int sorted_array[N]; for (int i = 0;i < N;i++) sorted_array[i] = i;
efficiency_sort=sorted_array;
quick_sort(sorted_array, 0, N - 1);
for (int i = 0;i < N;i++) {
printf("%d ", efficiency_sort[i]);
} printf("\n");
printf("Calculating\n");
int record[N]; record_max = record;
int temp_array[0];
searchMax(0, W, 0, 0, temp_array);
printf("==Result==\n");
printf("value: %ld\n", MAX);
char result[N];
for (int i = 0;i < N;i++) result[i] = '0';
for (int i = 0;i < record_size;i++) result[record_max[i]]++;
printf("combination: "); for (int i = 0;i < N;i++) printf("%c", result[i]); printf("\n");
return 0;
}
void swap (int *x, int *y) {
int temp;
temp = *x;
*x = *y;
*y = temp;
}
void quick_sort(int array[], int left,int right) {
int i,j,pivot;
if(left<right) {
pivot = array[(left+right)/2];
i = left;
j = right;
while(i <= j){
while((items+array[i])->efficiency > (items+pivot)->efficiency) i++;
while((items+array[j])->efficiency < (items+pivot)->efficiency) j--;
if(i <= j) swap(&array[i++], &array[j--]);
}
quick_sort(array, left, j);
quick_sort(array, i, right);
}
}
long int getUpperBound(int i, long int w) {
double max = 0, rw = (double) w;
for (int j = 0;j < N;j++) {
int index = efficiency_sort[j];
if (index < i) continue;
if ((items+index)->weight > rw) {
double temp = (double) (items+index)->value;
temp *= rw;
temp /= (double) (items+index)->weight;
max += temp;
break;
} else {
max += (items+index)->value;
rw -= (items+index)->weight;
}
}
return (long int) max;
}
long int searchMax(int i, long int w, long int sum, int rec_size, int record[]) {
if (i == N) {
if (sum > MAX) {
MAX = sum;
record_size = rec_size;
for(int j = 0;j < record_size;j++) record_max[j] = record[j];
}
return sum;
}
if (MAX >= getUpperBound(i, w) + sum) return -1;
int r1 = -1, r2 = -1;
if ((items+i)->weight<=w) {
int rec[rec_size + 1]; for (int j = 0;j < rec_size;j++) rec[j] = record[j];
rec[rec_size] = i;
r1 = searchMax(i+1,w-((items+i)->weight),sum+((items+i)->value), rec_size + 1, rec);
}
r2 = searchMax(i+1,w, sum, rec_size, record);
return r1 > r2 ? r1 : r2;
}
