硬币找零 DP 算法打印所有组合
Coin Change DP Algorithm Print All Combinations
这里很好地描述了经典的硬币找零问题:http://www.algorithmist.com/index.php/Coin_Change
这里我不仅要知道有多少种组合,还要打印出来。我在我的实现中使用了 link 中相同的 DP 算法,但我没有记录 DP[i][j] = count
的 DP table 中有多少组合,而是将组合存储在 table.所以我为此 DP 使用 3D 矢量 table。
我试图改进我的实现,注意到在查找 table 时,只需要最后一行的信息,所以我真的不需要总是存储整个 table。
不过我改进后的DP方案还是比较慢,所以我在想是不是我下面的实现有什么问题,还是可以进一步优化。谢谢!
您可以运行直接输入代码:
#include <iostream>
#include <stdlib.h>
#include <iomanip>
#include <cmath>
#include <vector>
#include <algorithm>
using namespace std;
int main(int argc, const char * argv[]) {
int total = 10; //total amount
//available coin values, always include 0 coin value
vector<int> values = {0, 5, 2, 1};
sort(values.begin(), values.end()); //I want smaller coins used first in the result
vector<vector<vector<int>>> empty(total+1); //just for clearing purpose
vector<vector<vector<int>>> lastRow(total+1);
vector<vector<vector<int>>> curRow(total+1);
for(int i=0; i<values.size(); i++) {
for(int curSum=0; curSum<=total; curSum++){
if(curSum==0) {
//there's one combination using no coins
curRow[curSum].push_back(vector<int> {});
}else if(i==0) {
//zero combination because can't use coin with value zero
}else if(values[i]>curSum){
//can't use current coin cause it's too big,
//so total combination for current sum is the same without using it
curRow[curSum] = lastRow[curSum];
}else{
//not using current coin
curRow[curSum] = lastRow[curSum];
vector<vector<int>> useCurCoin = curRow[curSum-values[i]];
//using current coin
for(int k=0; k<useCurCoin.size(); k++){
useCurCoin[k].push_back(values[i]);
curRow[curSum].push_back(useCurCoin[k]);
}
}
}
lastRow = curRow;
curRow = empty;
}
cout<<"Total number of combinations: "<<lastRow.back().size()<<endl;
for (int i=0; i<lastRow.back().size(); i++) {
for (int j=0; j<lastRow.back()[i].size(); j++) {
if(j!=0)
cout<<" ";
cout<<lastRow.back()[i][j];
}
cout<<endl;
}
return 0;
}
看来你复制的向量太多了:至少最后的else
可以重写为
// not using current coin
curRow[curSum] = lastRow[curSum];
const vector<vector<int>>& useCurCoin = curRow[curSum - values[i]]; // one less copy here
// using current coin
for(int k = 0; k != useCurCoin.size(); k++){
curRow[curSum].push_back(useCurCoin[k]);
curRow[curSum].back().push_back(values[i]); // one less copy here too.
}
即使清理可读curRow = empty;
,也可能会创建分配。
最好创建一个函数
void Clean(vector<vector<vector<int>>>& vecs)
{
for (auto& v : vecs) {
v.clear();
}
}
这里很好地描述了经典的硬币找零问题:http://www.algorithmist.com/index.php/Coin_Change
这里我不仅要知道有多少种组合,还要打印出来。我在我的实现中使用了 link 中相同的 DP 算法,但我没有记录 DP[i][j] = count
的 DP table 中有多少组合,而是将组合存储在 table.所以我为此 DP 使用 3D 矢量 table。
我试图改进我的实现,注意到在查找 table 时,只需要最后一行的信息,所以我真的不需要总是存储整个 table。
不过我改进后的DP方案还是比较慢,所以我在想是不是我下面的实现有什么问题,还是可以进一步优化。谢谢!
您可以运行直接输入代码:
#include <iostream>
#include <stdlib.h>
#include <iomanip>
#include <cmath>
#include <vector>
#include <algorithm>
using namespace std;
int main(int argc, const char * argv[]) {
int total = 10; //total amount
//available coin values, always include 0 coin value
vector<int> values = {0, 5, 2, 1};
sort(values.begin(), values.end()); //I want smaller coins used first in the result
vector<vector<vector<int>>> empty(total+1); //just for clearing purpose
vector<vector<vector<int>>> lastRow(total+1);
vector<vector<vector<int>>> curRow(total+1);
for(int i=0; i<values.size(); i++) {
for(int curSum=0; curSum<=total; curSum++){
if(curSum==0) {
//there's one combination using no coins
curRow[curSum].push_back(vector<int> {});
}else if(i==0) {
//zero combination because can't use coin with value zero
}else if(values[i]>curSum){
//can't use current coin cause it's too big,
//so total combination for current sum is the same without using it
curRow[curSum] = lastRow[curSum];
}else{
//not using current coin
curRow[curSum] = lastRow[curSum];
vector<vector<int>> useCurCoin = curRow[curSum-values[i]];
//using current coin
for(int k=0; k<useCurCoin.size(); k++){
useCurCoin[k].push_back(values[i]);
curRow[curSum].push_back(useCurCoin[k]);
}
}
}
lastRow = curRow;
curRow = empty;
}
cout<<"Total number of combinations: "<<lastRow.back().size()<<endl;
for (int i=0; i<lastRow.back().size(); i++) {
for (int j=0; j<lastRow.back()[i].size(); j++) {
if(j!=0)
cout<<" ";
cout<<lastRow.back()[i][j];
}
cout<<endl;
}
return 0;
}
看来你复制的向量太多了:至少最后的else
可以重写为
// not using current coin
curRow[curSum] = lastRow[curSum];
const vector<vector<int>>& useCurCoin = curRow[curSum - values[i]]; // one less copy here
// using current coin
for(int k = 0; k != useCurCoin.size(); k++){
curRow[curSum].push_back(useCurCoin[k]);
curRow[curSum].back().push_back(values[i]); // one less copy here too.
}
即使清理可读curRow = empty;
,也可能会创建分配。
最好创建一个函数
void Clean(vector<vector<vector<int>>>& vecs)
{
for (auto& v : vecs) {
v.clear();
}
}