本文共 1765 字，大约阅读时间需要 5 分钟。
我们需要解决一个经典的优化问题，即购买n张票时，使用最少数量的纸币。这是一种典型的动态规划问题，但需要结合贪心算法技术来解决约束条件下的问题。
机器一次性最多能购买k张票，因此我们需要分解问题，找到购买i张票所需的最小纸币数，并将其延伸到购买n张票的情况。
单次购买问题
首先，我们需要计算在最多购买k张票的情况下，购买i张票所需的最小纸币数。我们使用贪心算法来确定这一点。贪心算法从最大的票面开始尽可能多地使用，从而减少纸币总数。动态规划扩展
为了处理购买n张票的情况，我们将单次购买的结果进行动态规划扩展。我们使用一个数组minv2来存储购买i张票所需的最小纸币数。通过动态转移方程和多次状态转移，逐步计算出购买n张票的最优解。初始化
创建两个数组：minv1用于存储购买i张票所需的最小纸币数（i范围为1到k）；minv2用于存储购买i张票所需的最小纸币数（i范围扩展至1到n）。单次购买计算
使用贪心算法计算minv1数组。通过遍历所有可能的i值，确定购买i张票所需的最小纸币数。动态规划扩展
使用动态规划方法来计算minv2数组。通过递推式minv2[i] = min(minv2[i], minv2[i-j] + minv1[j])，将单次购买的结果逐步扩展到n次购买的情况。j的取值范围是从1到min(i,k)，确保不会超过购买次数限制。#includeusing namespace std;int V[6] = { 1, 5, 10, 20, 50, 100 };#define INF 0x3f3f3f3fint main() { int n, k, p; cin >> n >> k >> p; int minv1[1010] = { 0 }; int minv2[1010]; fill(minv2, minv2 + 1010, INF); minv2[0] = 0; minv1[0] = 0; for (int i = 1; i <= k; ++i) { int val = i * p; for (int j = 5; val > 0; --j) { if (val >= V[j]) { minv1[i] += V[j]; val -= V[j]; } } } for (int i = 1; i <= n; ++i) { int best = INF; for (int j = 1; j <= min(i, k); ++j) { if (minv2[i - j] + minv1[j] < best) { best = minv2[i - j] + minv1[j]; } } if (best < minv2[i]) { minv2[i] = best; } } cout << minv2[n] << endl; return 0;}
头部包含
包含了必要的头部文件，并使用了标准的输入输出流和常用功能。变量定义
读取输入参数n, k, p，并初始化了minv1和minv2数组。minv1用于存储单次购买的最小纸币数，minv2用于存储n次购买的最小纸币数。计算minv1
使用外层循环遍历i从1到k，内层循环从最大的票面开始尽可能多地使用，从而计算出购买i张票所需的最小纸币数。动态规划计算minv2
单次购买的基础上，通过递推式将其应用于n张票的情况。对于每个i，尝试所有可能的j值，从而找到最优解。输出结果
最后输出购买n张票所需的最小纸币数。通过以上步骤，我们成功地将问题分解并借助动态规划和贪心算法的结合，找到了最优解，确保购买n张票所需的纸币数最少。
转载地址：http://qkhtz.baihongyu.com/