【正经题解】新年趣事之打牌

这段代码通过动态规划的方法找到满足总重量的所有组合，然后判断是否有解以及是否存在多解，最后输出结果。

#include <bits/stdc++.h>
const int maxn = 1e5 + 10;
using namespace std;

int w[105];
int dp[maxn];
int path[maxn];
int n, m, sum;

void PT(int x) {
    if (x) {
        PT(x - w[path[x]]);
        printf(x == (sum - m) ? "%d\n" : "%d ", path[x]);
    }
}

int main() {
    // 输入剩下的牌的总重量和牌的数量
    scanf("%d %d", &m, &n);

    // 输入每一张牌的重量，并计算总重量
    for (int i = 1; i <= n; i++) {
        scanf("%d", &w[i]);
        sum += w[i];
    }

    // 初始化动态规划数组和路径数组
    dp[0] = 1;
    for (int i = 1; i <= n; i++) {
        for (int j = sum - m; j >= w[i]; j--) {
            dp[j] += dp[j - w[i]];
            if (dp[j] > 100) dp[j] = 10;
            if (!path[j] && dp[j - w[i]]) path[j] = i;
        }
    }

    // 判断是否有解
    if (!dp[sum - m]) printf("0\n");
    else if (dp[sum - m] > 1) printf("-1\n");
    else PT(sum - m);

    return 0;
}