本文共 1766 字，大约阅读时间需要 5 分钟。
为了解决这个问题，我们需要找到一个方法来计算在给定重量下，使用硬币的最小总价值。这个问题可以通过动态规划来解决，类似于背包问题，但目标是最小化总价值。
方法思路
问题分析：我们需要用给定的硬币组合，使得总重量等于V克，并且总价值最小。这里的V是填满猪的重量减去空猪的重量。 动态规划：我们使用动态规划来解决这个问题。动态规划的状态定义为 dp[i]，表示达到重量 i 克所需的最小价值。 初始化：dp[0] 初始化为 0，因为没有重量的价值为 0。其他状态初始化为无穷大，表示不可达。 更新状态：对于每个硬币，遍历所有可能的重量，从硬币的重量到目标重量 V，更新 dp 数组。 结果检查：检查 dp[V] 是否为无穷大，如果是，说明无法达到目标重量，否则输出最小价值。 解决代码
#include #include using namespace std;int main() { int t; scanf("%d", &t); while (t--) { int E, F; scanf("%d %d", &E, &F); int V = F - E; int n; scanf("%d", &n); vector > coins; for (int i = 0; i < n; ++i) { int P, W; scanf("%d %d", &P, &W); coins.push_back(make_pair(W, P)); } if (V == 0) { printf("The minimum amount of money in the piggy-bank is 0.\n"); continue; } vector dp(V + 1, INT_MAX); dp[0] = 0; for (auto& coin : coins) { int W = coin.first; int P = coin.second; for (int j = W; j <= V; ++j) { if (dp[j - W] != INT_MAX) { if (dp[j] > dp[j - W] + P) { dp[j] = dp[j - W] + P; } } } } if (dp[V] == INT_MAX) { printf("This is impossible.\n"); } else { printf("The minimum amount of money in the piggy-bank is %d.\n", dp[V]); } } return 0;}
代码解释
输入处理：读取测试用例数 t，然后逐个处理每个测试用例。读取 E 和 F，计算 V。 硬币处理：读取每个硬币的重量和价值，存储在 coins 列表中。 动态规划初始化：dp 数组初始化为 V+1 个元素，初始值为无穷大，除了 dp[0] 为 0。 更新 dp 数组：遍历每个硬币，更新每个可能的重量，尝试用当前硬币达到更小的价值。 结果输出：检查 dp[V] 是否为无穷大，输出结果或 "This is impossible."。 这个方法通过动态规划有效地解决了问题，确保在给定重量下找到最小的总价值。
转载地址：http://okio.baihongyu.com/