From 92d2da1251d9712ee86c733e648c0feceeb7d571 Mon Sep 17 00:00:00 2001
From: Iru Cai <mytbk920423@gmail.com>
Date: Thu, 19 Apr 2018 23:12:23 +0800
Subject: finish 2.1

---
 2.1/holstein.c | 78 ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
 1 file changed, 78 insertions(+)
 create mode 100644 2.1/holstein.c

(limited to '2.1/holstein.c')

diff --git a/2.1/holstein.c b/2.1/holstein.c
new file mode 100644
index 0000000..637a43a
--- /dev/null
+++ b/2.1/holstein.c
@@ -0,0 +1,78 @@
+/*
+ID: mytbk921
+LANG: C
+TASK: holstein
+*/
+
+#include <stdio.h>
+#include <string.h>
+#include <math.h>
+#include <stdlib.h>
+
+int vitamins[25];
+int feeds[15][25];
+int nv;
+int nf;
+
+static unsigned
+popcount(unsigned x)
+{
+	unsigned c = 0;
+	while (x) {
+		if (x&1) c++;
+		x >>= 1;
+	}
+	return c;
+}
+
+int main()
+{
+	FILE *fin = fopen("holstein.in", "r");
+	FILE *fout = fopen("holstein.out", "w");
+	int i, j;
+	unsigned scm, best, ans_n, tn;
+	int tmp_v[25];
+
+	fscanf(fin, "%d", &nv);
+	for (i=0; i<nv; i++)
+		fscanf(fin, "%d", &vitamins[i]);
+	fscanf(fin, "%d", &nf);
+	for (j=0; j<nf; j++) {
+		for (i=0; i<nv; i++)
+			fscanf(fin, "%d", &feeds[j][i]);
+	}
+
+	/* init: use all feeds */
+	best = (1<<nf)-1;
+	ans_n = nf;
+
+	for (scm=1; scm<(1<<nf)-1; scm++) {
+		tn = popcount(scm);
+		if (tn>=ans_n)
+			continue;
+		memset(tmp_v, 0, sizeof(tmp_v));
+		for (i=0; i<nf; i++) {
+			if (scm&(1<<i)) {
+				for (j=0; j<nv; j++)
+					tmp_v[j] += feeds[i][j];
+			}
+		}
+		for (i=0; i<nv; i++) {
+			if (tmp_v[i]<vitamins[i])
+				break;
+		}
+		if (i==nv) {
+			best = scm;
+			ans_n = tn;
+		}
+	}
+
+	fprintf(fout, "%d", ans_n);
+	for (i=0; i<nf; i++) {
+		if (best&(1<<i))
+			fprintf(fout, " %d", i+1);
+	}
+	fprintf(fout, "\n");
+	fclose(fout);
+	return 0;
+}
-- 
cgit v1.2.3