StackOverflow2013

Note that there are some explanatory texts on larger screens.

plurals

PO
text
Body
copied!<p>The other way, which is practical for small examples like the one you've got, is to use dynamic programming. One can build up a table of "optimal score if you use the first k subjects, and want credits to add up to T". The code's a bit messy because C doesn't make it particularly easy to have dynamically sized 2d arrays, but here's a solution. Probably your professor was expecting something along these lines.</p> <p>A small note, I divided all the credits (and the target credits of 120) by 10 because the common factor was redundant, but the code works just fine without that (it'll just use a tad more memory and time).</p> <pre><code>#include <stdio.h> #include <stdlib.h> int max(int a, int b) { return a > b ? a : b; } #define GET(t, i, j, n) ((t)[(i) * (n + 1) + j]) // optimize_marks takes arrays creds and marks (both of length n), // and finds a subset I of 0..(n-1) that maximizes // sum(i in I)creds[i]*marks[i], such that sum(i in I)creds[i] = total. void optimize_marks(size_t n, int *creds, int *marks, int total) { // tbl[k * (total + 1) + T] stores the optimal score using only the // first k subjects for a total credit score of T. // tbl[n * (total + 1) + total] will be the final result. // A score of -1 means that the result is impossible. int *tbl = malloc((n + 1) * (total + 1) * sizeof(int)); for (int i = 0; i <= n; i++) { for (int T = 0; T <= total; T++) { if (i == 0) { // With 0 subjects, the best score is 0 if 0 credits are // required. If more than 0 credits are required, the result // is impossible. GET(tbl, i, T, total) = -(T > 0); continue; } // One way to get T credits with the first i subjects is to // get T credits with the first (i-1) subjects. GET(tbl, i, T, total) = GET(tbl, i - 1, T, total); // The other way is to use the marks for the i'th subject // and get the rest of the credits with the first (i-1) subjects. // We have to check that it's possible to use the first (i-1) subjects // to get the remainder of the credits. if (T >= creds[i-1] && GET(tbl, i - 1, T - creds[i-1], total) >= 0) { // Pick the best of using and not using the i'th subject. GET(tbl, i, T, total) = max( GET(tbl, i, T, total), GET(tbl, i - 1, T - creds[i-1], total) + marks[i-1] * creds[i-1]); } } } int T = total; for (int i = n; i > 0; i--) { if (GET(tbl, i - 1, T, total) < GET(tbl, i, T, total)) { printf("%d %d %d\n", i, creds[i-1], marks[i-1]); T -= creds[i-1]; } } } int main(int argc, char *argv[]) { int creds[] = {6, 2, 2, 2, 1, 2, 1, 1, 1, 2, 2, 1}; int marks[] = {48, 77, 46, 82, 85, 43, 49, 73, 65, 48, 47, 51}; optimize_marks(12, creds, marks, 12); return 0; } </code></pre> <p>The program gives the solution as the ILP program:</p> <pre><code>12 1 51 11 2 47 10 2 48 9 1 65 8 1 73 5 1 85 4 2 82 2 2 77 </code></pre>

Querying!

Guidance

An individual column

Larger individual text columns get their own page to allow for proper reading.

SQuiL has stopped working due to an internal error.

If you are curious you may find further information in the browser console, which is accessible through the devtools (F12).

Reload