C 프로그래밍에서 지정된 크레딧으로 최고의 점수를 선택하는 방법은 무엇입니까?

다른 방법은 여러분이 가지고있는 것과 같은 작은 예제에 실용적인 방법으로 동적 프로그래밍을 사용하는 것입니다. "처음 k 과목을 사용하고 학점을 T까지 합산하려면 최적 점수"테이블을 만들 수 있습니다. C는 동적 크기의 2D 배열을 특별히 쉽게 만들지 못하기 때문에 코드가 약간 지저분하지만 여기에 해결책이 있습니다. 아마도 당신의 교수님은이 라인을 따라 뭔가를 기대하고 있었을 것입니다.

작은 메모, 공통 요소가 중복 되었기 때문에 모든 크레딧 (및 120의 목표 크레딧)을 10으로 나눴지만 코드는 그것 없이도 잘 작동합니다 (조금 더 많은 메모리와 시간을 사용합니다).

#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;
}

이 프로그램은 솔루션을 ILP 프로그램으로 제공합니다.

12 1 51
11 2 47
10 2 48
9 1 65
8 1 73
5 1 85
4 2 82
2 2 77