世界名画陈列馆问题（回溯法）的C++实现

以下是一个简单的回溯法实现世界名画陈列馆问题的 C 代码：

#include <stdio.h>
#define N 10

int n, m, k;
int w[N][N], x[N], sum[N], maxsum;
int bestx[N];

void backtracking(int t)
{
    if (t > n)
    {
        for (int i = 1; i <= n; i++)
            bestx[i] = x[i];
        maxsum = sum[n];
        return;
    }
    for (int i = 1; i <= m; i++)
    {
        if (sum[t - 1] + w[t][i] <= k)
        {
            x[t] = i;
            sum[t] = sum[t - 1] + w[t][i];
            backtracking(t + 1);
            x[t] = 0;
            sum[t] = sum[t - 1];
        }
    }
}

int main()
{
    printf("请输入陈列馆数量n，画作数量m和展厅容量k：");
    scanf("%d%d%d", &n, &m, &k);
    printf("请输入每幅画在每个陈列馆的分值：\n");
    for (int i = 1; i <= n; i++)
    {
        for (int j = 1; j <= m; j++)
        {
            scanf("%d", &w[i][j]);
        }
    }
    backtracking(1);
    printf("选取的陈列馆为：\n");
    for (int i = 1; i <= n; i++)
    {
        printf("%d ", bestx[i]);
    }
    printf("\n最大分值为：%d\n", maxsum);
    return 0;
}

该代码中，数组`w`表示每一幅画在每个陈列馆的分值，数组`x`表示选取的陈列馆，数组`sum`表示在选取前`i`个陈列馆并且容量不超过`k`的情况下的最大分值，变量`maxsum`表示最终的最大分值，数组`bestx`表示最终选取的陈列馆。

在`backtracking`函数中，`t`表示当前处理的陈列馆，首先判断是否已经选取完了所有的陈列馆，如果是，则更新最大分值和最优解，然后返回。如果未选完，则遍历陈列馆，尝试将当前的画作放到每个陈列馆中，如果容量不超过`k`，则继续递归处理下一个陈列馆。当递归返回时，需要回溯，将当前的陈列馆和分值撤销，以便处理下一个陈列馆。

在主函数中，先读入陈列馆数量、画作数量和展厅容量，然后读入每一幅画在每个陈列馆的分值，然后调用`backtracking`函数，最后输出选取的陈列馆和最大分值。