题解 | #W学长的零花钱#

该问题是典型的多重背包问题，不懂的可看该视频 https://www.bilibili.com/video/BV1xv411H7ST/？spm_id_from=333.999.0.0&vd_source=81678c8c7b5ba3c955908e3572e2335d

多重背包一般是求装满容量为j的背包的最大价值是多少，其递推公式为

dp[j] = max(dp[j], dp[j - weight[i]] + value[i])

而本题是求最少零钱个数,所以得变换两处：用min,且将value[i]改为+1(求的是零钱数目,而非价值)

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

int T, m;

int main() {
  cin >> T;
  while (T--) {
      vector<int> money{1, 5, 10};
      vector<int> nums(3);

      cin >> m;

      for (int i = 0;i < 3;i++)
          cin >> nums[i];

      vector<int> dp(m + 1, 101);  // 默认初始化得大于100，便于比较
      dp[0] = 0;  // 如果dp[0]也为101 的话，后⾯所有推导出来的值都是101了

      for (int i = 0;i < 3;i++)  // 遍历零钱的面值大小
          for (int k = 0;k < nums[i];k++)  // 遍历各个面值的零钱的数目
              for (int j = m;j >= money[i];j--)
                  dp[j] = min(dp[j], dp[j - money[i]] + 1);

	  // 当出现该情况时，则证明凑不出m
      if (dp[m] == 101)
          cout << -1 << endl;
      else
          cout << dp[m] << endl;  // 当dp[m]非101时，则是最小的零钱数
  }
  return 0;
}