感觉这题是不是数据太水,本来想练练打代码的速度,先打个朴素多重背包，然后再打优化，结果朴素直接交上去就AC了，有点搞。看题解都说普通版会超时，有点奇怪。 AC 代码:

#include <iostream>
#include <algorithm>
#include <cstring>
#include <vector>

using namespace std;

const int N = 210, M = 20010;

int n, m;
int b[N], c[N];
int dp[N][M];
int ans[N][M];

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    cin >> n;
    for (int i = 1; i <= n; i ++) cin >> b[i];
    for (int i = 1; i <= n; i ++) cin >> c[i];
    cin >> m;
    
    // dp[i][j], 只用前i种硬币, 凑j元, 最少需要的硬币数量
    
    memset(dp, 0x3f, sizeof(dp));
    for (int i = 0; i <= n; i ++) dp[i][0] = 0;
    
    for (int i = 1; i <= n; i ++)
        for (int j = 0; j <= m; j ++)
            for (int k = 0; k <= c[i] && k * b[i] <= j; k ++)
            {
                //dp[i][j] = min(dp[i][j], dp[i - 1][j - k * b[i]] + k);
                if (dp[i][j] > dp[i - 1][j - k * b[i]] + k)
                {
                    dp[i][j] = dp[i - 1][j - k * b[i]] + k;
                    ans[i][j] = k;
                }
            }
    
    
    cout << dp[n][m] << endl;
    
    vector<int> res;
    
    int v = m;
    for (int i = n; i >= 1; i --)
    {
        res.push_back(ans[i][v]);
        v -= ans[i][v] * b[i];
    }

    for (int i = res.size() - 1; i >= 0; i --) cout << res[i] << ' ';
    cout << endl;
    
    return 0;
}