货币系统类型问题，求解答

Question

请问有人会写这一题的代码吗？代码编写挺久了但总感觉思路不着边

给你n个钱币，每个钱币不仅有面值，还有重量，问最少多重的钱币可以恰好使得钱数为S？

输入格式
第一行：2个整数n,s，范围在[1 100]。
第二行：n个整数表示钱币相应的面值，每个数范围在[1, 100]
第三行：n个整数钱币相应的重量，每个数范围在[1, 10000]

输出格式
最少重量。(如果没有方案输出-1)

输入/输出例子1
输入：
6 8
3 2 3 7 2 1
5 3 5 13 3 1
输出：
12

样例解释
8=3+2+2+1，重量=5+3+3+1=12。

Answer 1

引自免费微信小程序：皆我百晓生

这是一个典型的背包问题，可以使用动态规划来解决。首先定义一个二维数组dp，其中dp[i][j]表示包含前i个硬币且总价值为j时所需的最小重量。初始化dp数组，当j小于硬币的面值时，dp[i][j] = dp[i - 1][j]（即不选当前硬币）；当j等于某个硬币的面值时，dp[i][j] = min(dp[i - 1][j], dp[i - 1][j - coins[i - 1]] + weights[i - 1])（选择或不选择当前硬币）。最终结果是dp[n][s]，如果dp[n][s] > s，则无解，返回-1。

以下是C++代码实现：

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

int main() {
    int n, s;
    cin >> n >> s;

    vector<int> values(n), weights(n);
    for (int i = 0; i < n; ++i) {
        cin >> values[i];
    }
    for (int i = 0; i < n; ++i) {
        cin >> weights[i];
    }

    // 初始化动态规划数组
    vector<vector<int>> dp(n + 1, vector<int>(s + 1, INT_MAX));
    dp[0][0] = 0;

    // 动态规划
    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= s; ++j) {
            if (values[i - 1] <= j) {
                dp[i][j] = min(dp[i - 1][j], dp[i - 1][j - values[i - 1]] + weights[i - 1]);
            } else {
                dp[i][j] = dp[i - 1][j];
            }
        }
    }

    // 输出结果
    if (dp[n][s] == INT_MAX) {
        cout << "-1" << endl;
    } else {
        cout << dp[n][s] << endl;
    }

    return 0;
}

这段代码首先读取输入数据，然后创建一个动态规划数组dp。接着通过两层循环遍历所有可能的情况，并根据题目描述更新dp数组中的值。最后检查dp[n][s]是否仍为最大整数值，如果是则表示没有满足条件的组合，输出-1；否则输出dp[n][s]作为答案。