爱做实验的平平经常使用天平称量重物，有一天他发现，在天平右边托盘中放置了 ww 克的重物时，在左边托盘中用好几种不同的砝码放置方案都可以让天平进入平衡状态。他很想知道，用手头 nn 个不同重量的砝码，究竟有多少种不同的放置方案能与这个 ww 克的重物平衡。 你能否编一个代码帮他解决这个问题?由于答案可能很大，所以只需输出方案总数除以 201809201809 的余数。

好的，这是一个比较典型的背包问题。我们可以使用动态规划的思想来解决。设 $f(i,j)$ 表示使用前 $i$ 个砝码，能否凑出重量为 $j$。则有转移方程：

$$
f(i,j) = f(i-1,j-w_i) \lor f(i-1,j)
$$

其中 $\lor$ 表示逻辑或操作，即两个值中有一个为真，结果就为真。边界条件为 $f(0,0)=1$，其余均为 $0$。最终答案即为 $\sum_{j=0}^{w}f(n,j)$，其中 $w$ 是重物的重量，$n$ 是砝码的个数。最后再对答案取模即可。

下面是对应的 Python 代码实现：

w, n = map(int, input().split())
weights = list(map(int, input().split()))
MOD = 201809201809

f = [[0] * (w + 1) for _ in range(n + 1)]
f[0][0] = 1

for i in range(1, n + 1):
    for j in range(w + 1):
        f[i][j] = f[i-1][j]
        if j >= weights[i-1]:
            f[i][j] |= f[i-1][j-weights[i-1]]

ans = sum(f[n]) % MOD
print(ans)

注意，这里的第二行输入了重量和砝码个数，接下来的一行输入了每个砝码的重量。

相关问题

爱做实验的平平经常使用天平称量重物，有一天他发现，在天平右边托盘中放置了 w 克的重物时，在左边托盘中用好几种不同的砝码放置方案都可以让天平进入平衡状态。他很想知道，用手头 n 个不同重量的砝码，究竟有多少种不同的放置方案能与这个 w 克的重物平衡。 你能否编一个代码帮他解决这个问题?由于答案可能很大，所以只需输出方案总数除以 201809 的余数。使用c++解决

这是一个经典的背包问题，可以使用动态规划来解决。设 $dp[i][j]$ 表示用前 $i$ 个砝码能否组成重量为 $j$ 的方案数，则有状态转移方程：

$$dp[i][j] = (dp[i-1][j-w_i] + dp[i-1][j])\%201809$$

其中 $w_i$ 表示第 $i$ 个砝码的重量。

最终的答案为 $dp[n][w]$，其中 $n$ 表示砝码的个数。

下面是 C++ 代码实现：

#include <iostream>
#include <cstring>
using namespace std;

const int maxn = 1005;
const int mod = 201809;

int dp[maxn][maxn];

int main() {
    int n, w;
    cin >> n >> w;
    memset(dp, 0, sizeof(dp));
    dp[0][0] = 1;
    for (int i = 1; i <= n; i++) {
        int wi;
        cin >> wi;
        for (int j = 0; j <= w; j++) {
            dp[i][j] = dp[i-1][j];
            if (j >= wi) {
                dp[i][j] = (dp[i][j] + dp[i-1][j-wi]) % mod;
            }
        }
    }
    cout << dp[n][w] << endl;
    return 0;
}

用c程序解决如下问题，平平今天又有早八，由于他喜欢卡点到，所以只给自己留了T分钟的时间吃饭。校六餐厅有n道菜，每道菜有一个快乐值v和用餐时间t，意为平平可以花t分钟吃掉这道菜，然后获得v的快乐值。但是如果吃早饭的时间太长了，导致他迟到了他也会感到不开心，具体的，如果t > T,他获得的快乐值就是v-(t-T)。现在请你计算平平吃掉某一道菜能获得的最大快乐值，输入如下第一行两个整数n,T,接下来n行每行两个数表示每道菜的快乐值和用餐时间。n<=100000

以下是我用C语言编写的解决方案：

#include <stdio.h>

int main() {
    int n, T;
    scanf("%d%d", &n, &T);
    int v[n], t[n], max_v = 0;
    for (int i = 0; i < n; i++) {
        scanf("%d%d", &v[i], &t[i]);
        if (t[i] > T) {
            v[i] = v[i] - (t[i] - T);
        }
        if (v[i] > max_v) {
            max_v = v[i];
        }
    }
    printf("%d", max_v);
    return 0;
}

该程序通过循环读入每道菜的快乐值和用餐时间，并判断用餐时间是否超过了平平的时间限制。如果超过了，就将快乐值减去超出的时间。最后，该程序输出所有菜品中快乐值最大的那道菜的快乐值。