题目大意：给出要买可乐的数量， 以及1元，5元和10元硬币的数量， 每瓶可乐8元，每次照钱会按照最少硬币的方式找回， 问如何投币可使得投入的硬币数最少， 输出最少硬币值。
解题思路：记忆化搜索， 因为可乐每购买一次便要找会硬币，所以对与每个状态考虑的情况比并不是很多。
注意：1、每够买一次可乐便会找回一次硬币，所以不用考虑的太复杂。
2、题目中虽然说1元不超过500个，但是开的记录数组一定要比500大，大约700左右，因为要考虑找回金额的情况。
#include <stdio.h>#include <string.h>#define min(a,b) (a) < (b) ? (a) : (b)const int MAX = 1 << 30;int vis[705][205][105], dp[705][205][105];int solve(int c, int n1, int n5, int n10) { int&cnt = dp[n1][n5][n10]; int& flag = vis[n1][n5][n10]; if (flag) return cnt; else if (c == 0) { flag = 1; cnt = 0; return cnt; } else { cnt = MAX; if (n1 >= 8) cnt = min(cnt, solve(c - 1, n1 - 8, n5, n10) + 8); if (n5 >= 1 && n1 >= 3) cnt = min(cnt, solve(c - 1, n1 - 3, n5 - 1, n10) + 4); if (n5 >= 2) cnt = min(cnt, solve(c - 1, n1 + 2, n5 - 2, n10) + 2); if (n10 >= 1) cnt = min(cnt, solve(c - 1, n1 + 2, n5, n10 - 1) + 1); if (n10 >= 1 && n1 >= 3) cnt = min(cnt, solve(c - 1, n1 - 3, n5 + 1, n10 - 1) + 4); flag = 1; return cnt; }}int main() { int cas; scanf("%d", &cas); while (cas--) { int c, n1, n5, n10; scanf("%d%d%d%d", &c, &n1, &n5, &n10); memset(vis, 0, sizeof(vis)); printf("%d\n", solve(c, n1, n5, n10)); } return 0;}再分享一下我老师大神的人工智能教程吧。零基础！通俗易懂！风趣幽默！还带黄段子！希望你也加入到我们人工智能的队伍中来！https://blog.csdn.net/jiangjunshow