c - c语言编程如何选择指定学分的最佳分数？

Question

我想制作一个程序，从best(highest) 120 credits module中获取加权平均值(公式=(mark*(credits对应于它))/total credits) 来自以下标记和学分(学分对应模块):

module[12]={48, 77, 46, 82, 85, 43, 49, 73, 65, 48, 47, 51}

credits[12]={60, 20, 20, 20, 10, 20, 10, 10, 10, 20, 20, 10}

我做的是对数组进行冒泡排序，让数组按照降序排列，知道哪个分数高，如下图:

module[12]={85, 82, 77, 73, 65, 51, 49, 48, 48, 47, 46, 43}

credits[12]={10, 20, 20, 10, 10, 10, 10, 60, 20, 20, 20, 20}

然后我需要从排序数组中选择最好的 120 个学分模块以便加权平均值最大，但我不知道从哪里开始。 =(

有人帮帮我!非常感谢!

编辑:我尝试自己编写代码，并最终得到以下代码，它可以工作，但对于某些特殊情况，它停止工作 =(

float credits=0, result=0;
n=0;

struct{
    float credits;
    float result;
    float n;
    float addpoint;
}point;

while (credits < 120){
        credits+=credits[n];
        result+=(result[n]*credits[n]);
        n++; 
    }

    if (credits != 120){
        credits -= credits[n-1];
        result -= (result[n-1]*credits[n-1]);

        point.credits = credits;
        point.result = result;
        point.n = (n-1)-1;

        point.addpoint = n;

again:  while (credits < 120){
            credits+=credits[n];
            result+=(result[n]*credits[n]);
            n++;
        }

        if (credits != 120){
            point.credits -= credits[point.n-1];
            point.result -= result[point.n-1]*credits[point.n-1];
            point.n--;

            credits = point.credits;
            result = point.result;
            n = point.addpoint-1;

            goto again;
        }
    }

编辑:

已解决。应用glpk使用背包问题代码/整数线性规划

Answer 1

另一种方法(对于像您已有的例子这样的小示例很实用)是使用动态规划。可以建立一个“如果你使用前k个科目并希望学分加起来为T”的最佳分数表。代码有点乱，因为 C 并没有使动态大小的二维数组变得特别容易，但这里有一个解决方案。可能您的教授正在期待类似的东西。

请注意，我将所有学分(以及目标学分 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