硬币找零DP算法打印所有组合 [英] Coin Change DP Algorithm Print All Combinations

问题描述

经典的硬币找零问题以及描述如下： http://www.algorithmist.com/的index.php / Coin_Change

在这里，我想不仅知道有多少组合也有，但也打印出所有的人。我使用的是同一个DP算法，而不是记录有多少组合DP表中的 DP [I] [J] =数清我实现了链接，但，我存储在表中的组合。所以我用这个DP表中的三维矢量。

我想提高我的执行注意到，查表时，从最后一排唯一信息是必要的，所以我并不真的需要始终将整个表。

但我提高了DP的解决方案似乎仍然有点慢，所以我想知道如果有一个在我执行下面的一些问题，也可以有更多的优化。谢谢！

您可以直接运行code：

 的#include＆LT;的iostream＆GT;
＃包括＆LT; stdlib.h中＆GT;
＃包括＆LT;了iomanip＆GT;
＃包括＆LT; CMATH＆GT;
＃包括＆LT;载体＆GT;
＃包括＆LT;算法＆GT;
使用名字空间std;

INT主（INT ARGC，为const char * argv的[]）{

    INT总= 10; //总金额
    //可用硬币值，总是包含0硬币价值
    矢量＆lt; int的＆GT;值= {0,5，2，1};
    排序（values​​.begin（），values​​.end（））; //我想小硬币最早采用结果

    矢量＆lt;矢量＆lt;矢量＆lt; INT＆GT;＆GT;＆GT;空（总+ 1）; //只是为了清除的目的
    矢量＆lt;矢量＆lt;矢量＆lt; INT＆GT;＆GT;＆GT; LASTROW（总+ 1）;
    矢量＆lt;矢量＆lt;矢量＆lt; INT＆GT;＆GT;＆GT; curRow（总+ 1）;


    的for（int i = 0; I＆LT; values​​.size（）;我++）{


        对于（INT curSum = 0; curSum＆LT; =总; curSum ++）{
            如果（curSum == 0）{
                //还有不使用硬币一个组合
                curRow [curSum] .push_back（矢量＆lt; INT＆GT; {}）;

            }否则，如果（我== 0）{
                //零组合，因为不能使用硬币的价值为零

            }否则如果（值[I]≥curSum）{
                //不能用当前的硬币因为它太大了，
                //当前款项，总的组合是相同的，而无需使用它
                curRow [curSum] = LASTROW [curSum]

            }其他{
                //不使用当前的硬币
                curRow [curSum] = LASTROW [curSum]
                矢量＆lt;矢量＆lt; INT＆GT;＆GT; useCurCoin = curRow [curSum值[I]];

                //使用当前的硬币
                对于（INT K = 0; K＆LT; useCurCoin.size（）; k ++）{

                    useCurCoin [k]的.push_back（值[I]）;
                    curRow [curSum] .push_back（useCurCoin [K]）;
                }
            }
        }

        LASTROW = curRow;
        curRow =空;
    }

    COUT＆LT;＆LT;组合总数：＆LT;＆LT; lastRow.back（）的大小（）＆LT;＆LT; ENDL;
    的for（int i = 0; I＆LT; lastRow.back（）的大小（）;我++）{
        对于（INT J = 0; J＆LT; lastRow.back（）[我] .size（）; J ++）{
            如果（j！= 0）
                COUT＆LT;＆LT;;
            COUT＆LT;＆LT; lastRow.back（）[I] [J]。
        }
        COUT＆LT;＆LT; ENDL;
    }
    返回0;
}
 

解决方案

看来你复制了太多的载体：至少在过去的其他可以写成

  //没有使用当前的硬币
curRow [curSum] = LASTROW [curSum]
常量矢量＆lt;矢量＆lt; INT＆GT;＆GT;＆安培; useCurCoin = curRow [curSum  - 值[I]]; //一个副本在这里少

//使用当前的硬币
对于（INT K = 0; k = useCurCoin.size（）;！k来++）{
    curRow [curSum] .push_back（useCurCoin [K]）;
    。curRow [curSum] .back（）的push_back（值[I]）; //一个副本在这里少了。
}
 

即使是可读的清洁 curRow =空; ，可能造成分配。 最好创建一个函数

 无效清洁（矢量＆lt;矢量＆lt;矢量＆lt; INT＆GT;＆GT;＆GT;＆安培;血管内皮细胞）
{
    为（自动＆安培;五：血管内皮细胞）{
        v.clear（）;
    }
}
 

The classic coin change problem is well described here: http://www.algorithmist.com/index.php/Coin_Change

Here I want to not only know how many combinations there are, but also print out all of them. I'm using the same DP algorithm in that link in my implementation but instead of recording how many combinations in the DP table for DP[i][j] = count, I store the combinations in the table. So I'm using a 3D vector for this DP table.

I tried to improve my implementation noticing that when looking up the table, only information from last row is needed, so I don't really need to always store the entire table.

However my improved DP solution still seems quite slow, so I'm wondering if there's some problem in my implementation below or there can be more optimization. Thanks!

You can run the code directly:

#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;
}

解决方案

It seems that you copy too many vectors: at least the last else can be rewritten as

// 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.
}

Even if it is readable to clean curRow = empty;, that may create allocation. Better to create a function

void Clean(vector<vector<vector<int>>>& vecs)
{
    for (auto& v : vecs) {
        v.clear();
    }
}

这篇关于硬币找零DP算法打印所有组合的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！