我是动态编程的新手(和C++，但我有更多的经验，有些事情我还不知道)。如何将LIMITED COINS添加到硬币更改问题中(请参阅下面的代码-有点乱，但我仍在处理中)。我有一个变量nr[100]，它记录硬币的数量(也在我的read_values()中创建了一些条件)。我不知道在我的代码中哪里可以使用它。
代码认为我们有无限的硬币供应(我不希望这样)。它是用自下而上的方法(动态编程)制作的。
我的代码灵感来自这个视频：Youtube
#include <iostream>
using namespace std;
int C[100], b[100], n, S, s[100], nr[100], i, condition=0, ok=1;
void read_values() //reads input
{
cin >> n; // coin types
cin >> S; // amount to change
for (i=1; i<=n; i++)
{
cin >> b[i]; //coin value
cin>>nr[i]; //coin amount
if(nr[i]==0)b[i]=0; //if there are no coin amount then the coin is ignored
condition+=b[i]*nr[i]; //tests to see if we have enough coins / amount of coins to create a solution
if(b[i]>S)
{
b[i]=0;
}
}
if(S>condition)
{
cout<<endl;
cout<<"Impossible!";
ok=0;
}
}
void payS()
{
int i, j;
C[0] = 0; // if amount to change is 0 then the solution is 0
for (j=1; j<=S; j++)
{
C[j] = S+1;
for (i=1; i<=n; i++)
{
if (b[i] <= j && 1 + C[j - b[i]] < C[j])
{
C[j] = 1 + C[j - b[i]];
s[j] = b[i];
}
}
}
cout << "Minimum ways to pay the amount: " << C[S] << endl;
}
void solution(int j)
{
if (j > 0)
{
solution(j - s[j]);
cout << s[j] << " ";
}
}
int main()
{
read_values();
if(ok!=0)
{
payS();
cout << "The coins that have been used are: ";
solution(S);
}
}
我的工作假设是，您需要使用nbr表为正整数值amount生成更改，其中nbr[n]是值为n的可用硬币数。我还假设nbr[0]实际上毫无意义，因为它只代表没有价值的硬币。
大多数动态编程问题通常在选择选项a与选项B的二元决策上重复出现；选择这个"；另一个是"；不要选择这个，而使用可用集合的其余部分；。这个问题真的没什么不同。
首先，让我们解决没有缓存的递归动态问题。
我将用一个称为"cointable"的数据结构来替换您的nbr变量。这用于跟踪可用的硬币集和为任何给定的解决方案路径选择的硬币集：
struct cointable
{
static const int MAX_COIN_VALUE = 100;
int table[MAX_COIN_VALUE+1]; // table[n] maps "coin of value n" to "number of coins availble at amount n"
int number; // number of coins in table
};
cointable::table实际上与您的nbr阵列是一样的。coinbase::number是表中值的总和。它不用于跟踪可用的硬币，但用于跟踪更好的解决方案。
现在我们可以介绍不使用查找缓存的递归解决方案。
递归的每一步都是这样做的：
在一组可用硬币中寻找价值最高的硬币，该硬币不大于解决的目标金额
重复选项A：选择从步骤1中选择的硬币。现在使用减少的可用硬币集(递归)求解减少的金额。
在选项B上重复：不要选择这枚硬币，而是使用第一枚价值低于步骤1的硬币进行重复。
比较2和3的递归结果。选择使用较少硬币的
以下是代码-不使用最佳查找缓存
bool generateChange(int amount, cointable& available, cointable& solution, int maxindex)
{
if ((maxindex == 0) || (amount < 0))
{
return false;
}
if (amount == 0)
{
return true;
}
int bestcoin = 0;
// find the highest available coin that not greater than amount
if (maxindex > amount)
{
maxindex = amount;
}
// assert(maxindex <= cointable::MAX_COIN_VALUE)
for (int i = maxindex; i >= 1; i--)
{
if (available.table[i] > 0)
{
bestcoin = i;
break;
}
}
if (bestcoin == 0)
{
return false; // out of coins
}
// go down two paths - one with picking this coin. Another not picking it
// option 1
// pick this coin (clone available and result)
cointable a1 = available;
cointable r1 = solution;
a1.table[bestcoin]--;
r1.table[bestcoin]++;
r1.number++;
bool result1 = generateChange(amount - bestcoin, a1, r1, bestcoin);
// option2 - don't pick this coin and start looking for solutions with lesser
// coins (not the use of references for a2 and r2 since we haven't changed anything)
cointable& a2 = available;
cointable& r2 = solution;
bool result2 = generateChange(amount, a2, r2, bestcoin - 1);
bool isSolvable = result1 || result2;
if (!isSolvable)
{
return false;
}
// note: solution and r2 are the same object, no need to reassign solution=r2
if (
((result1 && result2) && (r1.number < r2.number))
|| (result2 == false)
)
{
solution = r1;
}
return true;
}
然后快速演示如何在较大面额的硬币数量有限的情况下计算128美分的零钱：{1:100，5:20，10:10，25:1，50:1}
int main()
{
cointable available = {}; // zero-init
cointable solution = {}; // zero-init
available.table[1] = 100;
available.table[5] = 20;
available.table[10] = 10;
available.table[25] = 1;
available.table[50] = 1;
int amount = 128;
bool result = generateChange(amount, available, solution, cointable::MAX_COIN_VALUE);
if (result == true)
{
for (int i = 1; i < 100; i++)
{
if (solution.table[i] > 0)
{
std::cout << i << " : " << solution.table[i] << "n";
}
}
}
else
{
cout << "no solutionn";
}
}
这应该奏效。而且，对于大多数人来说，这可能足够快了，因为他们对一美元以下的任何东西都进行了更改，所以不需要缓存。所以我们有可能就此打住，就此结束。
我要在这里停下来
我开始研究一种解决方案；高速缓存"；以避免重复出现。但在对其进行基准测试并研究算法如何快速找到最佳解决方案后，我不太确定缓存是否有必要。我最初尝试为可解和不可解的解决方案插入缓存表，这只会使代码变慢。我需要研究如何让它发挥作用——如果有必要的话。
也许您希望我们修复您的代码，但我实现了自己版本的解决方案。希望我自己的版本对你有用，至少在教育方面是这样。
当然，我使用了动态编程的方法。
我保留了一个可能构成变化的向量。每一个下一个和都是由之前的和加上几个相同价值的硬币组成的。
还保留了使用过的硬币的历史，这使我们能够将每一次更改还原为特定硬币的组合。
代码之后，您可以看到控制台输出，其中显示了用硬币2x4、3x3、5x2、10x1组成零钱13的示例(此处第二个数字是硬币数量)。
在main()函数开始时，输入硬币及其数量在coins向量中给定，您可以用任何您想要的东西填充这个向量，例如通过控制台用户输入。需要表示的变化在变量change内给出。
不要忘记在代码和控制台输出后查看Post-Scriptum(PS.)，它有关于算法的更多细节。
以下完整代码：
在线试用！
#include <cstdint>
#include <vector>
#include <unordered_map>
#include <set>
#include <algorithm>
#include <functional>
#include <iostream>
using u32 = uint32_t;
using u64 = uint64_t;
int main() {
std::vector<std::pair<u32, u32>> const coins =
{{2, 4}, {3, 3}, {5, 2}, {10, 1}};
u32 const change = 13;
std::vector<std::unordered_map<u32, std::pair<u64, std::set<u32>>>>
sums = {{{0, {1, {}}}}};
for (auto [coin_val, coin_cnt]: coins) {
sums.push_back({});
for (auto const & [k, v]: sums.at(sums.size() - 2))
for (size_t icnt = 0; icnt <= coin_cnt; ++icnt) {
auto & [vars, prevs] = sums.back()[k + coin_val * icnt];
vars += v.first;
prevs.insert(icnt);
}
}
std::vector<std::pair<u32, u32>> path;
std::vector<std::vector<std::pair<u32, u32>>> paths;
std::function<bool(u32, u32, u32)> Paths =
[&](u32 sum, u32 depth, u32 limit){
if (sum == 0) {
paths.push_back(path);
std::reverse(paths.back().begin(), paths.back().end());
return paths.size() < limit;
}
auto const coin = coins.at(depth - 1).first;
auto const & [_, prevs] = sums.at(depth).at(sum);
for (auto const cnt: prevs) {
if (cnt > 0)
path.push_back({coin, cnt});
if (!Paths(sum - coin * cnt, depth - 1, limit))
return false;
if (cnt > 0)
path.pop_back();
}
return true;
};
if (!sums.back().count(change)) {
std::cout << "Change " << change
<< " can NOT be represented." << std::endl;
return 0;
}
std::cout << "Change " << change << " can be composed "
<< std::get<0>(sums.back().at(change)) << " different ways." << std::endl;
Paths(change, coins.size(), 20);
std::cout << "First " << paths.size() << " variants:" << std::endl;
for (auto const & path: paths) {
std::cout << change << " = ";
for (auto [coin, cnt]: path)
std::cout << coin << "x" << cnt << " + ";
std::cout << std::endl;
}
}
输出：
Change 13 can be composed 5 different ways.
First 5 variants:
13 = 2x2 + 3x3 +
13 = 2x4 + 5x1 +
13 = 2x1 + 3x2 + 5x1 +
13 = 3x1 + 5x2 +
13 = 3x1 + 10x1 +
PS正如您可能已经注意到的，算法的主要动态编程部分非常小，只有以下几行：
std::vector<std::unordered_map<u32, std::pair<u64, std::set<u32>>>>
sums = {{{0, {1, {}}}}};
for (auto [coin_val, coin_cnt]: coins) {
sums.push_back({});
for (auto const & [k, v]: sums.at(sums.size() - 2))
for (size_t icnt = 0; icnt <= coin_cnt; ++icnt) {
auto & [vars, prevs] = sums.back()[k + coin_val * icnt];
vars += v.first;
prevs.insert(icnt);
}
}
此部分保留所有当前可组合的总和(更改)。Algo从0的货币变化开始，然后将1乘1的硬币递增到所有可能的当前变化(总和)，从而形成新的总和(包括这个新硬币)。
每个和都有一个计数器，记录所有可能的组合方式，并记录导致这个和的所有最后硬币。最后一组硬币可以进行回溯，以恢复硬币的具体组合，而不仅仅是计算这个总数的方法。