【币值最大化问题】

• 1. 问题描述
• 2. 解决方案 --- 动态规划

1. 问题描述

给定一排n个硬币，其面值均为正整数c1，c2，…，cn，这些整数并不一定两两不同。请问如何选择硬币，使得在其原始位置互不相邻的条件下，所选硬币的总金额最大。

2. 解决方案 — 动态规划

• 解题思路：
  我们可以将问题划分为取最后一枚硬币和不取最后一枚硬币。根据不相邻这一条件，若取最后一枚硬币，则我们继续判断前n-2枚硬币中的币值总和最大问题；若不取最后一枚，则我们继续判断前n-1枚硬币中的币值总和最大问题。

f[0]=0; f[1]=arr[1]; f[n]=max(f[n-2]+arr[n],f[n-1]); f[n]: 有n个硬币时币值总和最大值。

• 代码演示:

#include <iostream> #include <algorithm> using namespace std; int main() {int n;cout << "请输入硬币的总数（n）：";cin >> n;int *arr = (int *)malloc((n + 1) * sizeof(int));//分配空间，存储数据（可以当成数组）for (int i = 1; i <= n; i++){cin >> arr[i];}int *f = (int *)malloc((n + 1) * sizeof(int));//分配空间，存储数据（可以当成数组）f[0] = 0;f[1] = arr[1];for (int i = 2; i <= n; i++){f[i] = max(f[i - 2] + arr[i], f[i - 1]);//i个硬币时，最大金额f[i]=包括arr[i]与不包括arr[i]中的最大值}cout << "总金额最大为：";cout << f[n] << endl;cout << "分别是：" << endl;//通过回溯法，得到选择的硬币int *arr2 = (int *)malloc((n + 1) * sizeof(int));//分配空间，存储数据（可以当成数组）int num = 0;for (int i = n; i >= 1; i--){if (f[i] == f[i - 1])//判断f[i]是否等于f[i-1]，若等于即没有选择arr[i]，反之则选择了{arr2[num++] = arr[--i];}else{arr2[num++] = arr[i--];}}sort(arr2, arr2 + num);for (int i = 0; i < num; i++){cout << arr2[i] << " ";}cout << endl;return 0; }

运行结果如下：

总结

以上是生活随笔为你收集整理的【币值最大化问题】的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。