Skip to main content
added 754 characters in body
Source Link
Errorsatz
  • 1.4k
  • 8
  • 9
std::set<int> sums;
for(int c = 0; c < coins.size(); ++c)
{
    // Include zero on the initial list, but not subsequent ones
    if(sums.empty()) 
    {
        for(int q = 0; q <<= quantity[c]; ++q) 
        {
            sums.insert(q * coins[c]);
        }
    }
    else
    {
        std::vector<int> current(sums.begin(), sums.end());
        for(int q = 1; q <<= quantity[c]; ++q)
        {
            for(autoint sum : current) 
            {
                sums.insert(sum + q * coins[c]);
            }
        }
    }
}         
std::vector<int> sums;
for(int c = 0; c < coins.size(); ++c)
{
    // Include zero on the initial list, but not subsequent ones
    if(sums.empty()) 
    {
        for(int q = 0; q <= quantity[c]; ++q) 
        {
            sums.push_back(q * coins[c]);
        }
    }
    else
    {
        int oldSize = sums.size();
        for(int q = 1; q <= quantity[c]; ++q)
        {
            for(int i = 0; i < oldSize; ++i) 
            {
                sums.push_back(sums[i] + q * coins[c]);
            }
        }
    }
}  

std::sort(sums.begin(), sums.end());
sums.erase(std::unique(sums.begin(), sums.end()), sums.end());
std::set<int> sums;
for(int c = 0; c < coins.size(); ++c)
{
    // Include zero on the initial list, but not subsequent ones
    if(sums.empty()) 
    {
        for(int q = 0; q < quantity[c]; ++q) 
        {
            sums.insert(q * coins[c]);
        }
    }
    else
    {
        std::vector<int> current(sums.begin(), sums.end());
        for(int q = 1; q < quantity[c]; ++q)
        {
            for(auto sum : current) 
            {
                sums.insert(sum + q * coins[c]);
            }
        }
    }
}         
std::set<int> sums;
for(int c = 0; c < coins.size(); ++c)
{
    // Include zero on the initial list, but not subsequent ones
    if(sums.empty()) 
    {
        for(int q = 0; q <= quantity[c]; ++q) 
        {
            sums.insert(q * coins[c]);
        }
    }
    else
    {
        std::vector<int> current(sums.begin(), sums.end());
        for(int q = 1; q <= quantity[c]; ++q)
        {
            for(int sum : current) 
            {
                sums.insert(sum + q * coins[c]);
            }
        }
    }
}         
std::vector<int> sums;
for(int c = 0; c < coins.size(); ++c)
{
    // Include zero on the initial list, but not subsequent ones
    if(sums.empty()) 
    {
        for(int q = 0; q <= quantity[c]; ++q) 
        {
            sums.push_back(q * coins[c]);
        }
    }
    else
    {
        int oldSize = sums.size();
        for(int q = 1; q <= quantity[c]; ++q)
        {
            for(int i = 0; i < oldSize; ++i) 
            {
                sums.push_back(sums[i] + q * coins[c]);
            }
        }
    }
}  

std::sort(sums.begin(), sums.end());
sums.erase(std::unique(sums.begin(), sums.end()), sums.end());
Fix for when quantity[0] == 0
Source Link
Errorsatz
  • 1.4k
  • 8
  • 9

Instead of calculating each combination recursively, you can build up the list one coinage type at a time. This would involve fewer iterations in the case that any combinations form the same total, and more importantly wouldn't require adding up each combination separately. For example:

std::set<int> sums;
for(int c = 0; c < coins.size(); ++c)
{
    // InitialInclude setzero includeson zerothe initial list, othersbut don'tnot subsequent ones
std::set<int> sums;   if(sums.empty()) 
    {
        for(int q = 0; q < quantity[0];quantity[c]; ++q) 
        {
            sums.insert(q * coins[0]coins[c]);
        }
 
for(int c = 1; c}
 < coins.size(); ++c) else
    {
        std::vector<int> current(sums.begin(), sums.end());
        for(int q = 1; q < quantity[c]; ++q)
        {
            for(auto sum : current) 
            {
                sums.insert(sum + q * coins[c]);
            }
        }
    }
}         

Using a vector instead of a set to accumulate sums (removing duplicates at the end) might be faster, and would eliminate the need for a temporary copy (current). However, it wouldn't eliminate the redundant loops based off the same total, so some measurements would be needed to see which is better.

Instead of calculating each combination recursively, you can build up the list one coinage type at a time. This would involve fewer iterations in the case that any combinations form the same total, and more importantly wouldn't require adding up each combination separately. For example:

// Initial set includes zero, others don't
std::set<int> sums;
for(int q = 0; q < quantity[0]; ++q) 
{
    sums.insert(q * coins[0]);
}
 
for(int c = 1; c < coins.size(); ++c)
{
    std::vector<int> current(sums.begin(), sums.end());
    for(int q = 1; q < quantity[c]; ++q)
    {
        for(auto sum : current) 
        {
            sums.insert(sum + q * coins[c]);
        }
    }
}         

Instead of calculating each combination recursively, you can build up the list one coinage type at a time. This would involve fewer iterations in the case that any combinations form the same total, and more importantly wouldn't require adding up each combination separately. For example:

std::set<int> sums;
for(int c = 0; c < coins.size(); ++c)
{
    // Include zero on the initial list, but not subsequent ones
    if(sums.empty()) 
    {
        for(int q = 0; q < quantity[c]; ++q) 
        {
            sums.insert(q * coins[c]);
        }
    }
    else
    {
        std::vector<int> current(sums.begin(), sums.end());
        for(int q = 1; q < quantity[c]; ++q)
        {
            for(auto sum : current) 
            {
                sums.insert(sum + q * coins[c]);
            }
        }
    }
}         

Using a vector instead of a set to accumulate sums (removing duplicates at the end) might be faster, and would eliminate the need for a temporary copy (current). However, it wouldn't eliminate the redundant loops based off the same total, so some measurements would be needed to see which is better.

Source Link
Errorsatz
  • 1.4k
  • 8
  • 9

Instead of calculating each combination recursively, you can build up the list one coinage type at a time. This would involve fewer iterations in the case that any combinations form the same total, and more importantly wouldn't require adding up each combination separately. For example:

// Initial set includes zero, others don't
std::set<int> sums;
for(int q = 0; q < quantity[0]; ++q) 
{
    sums.insert(q * coins[0]);
}

for(int c = 1; c < coins.size(); ++c)
{
    std::vector<int> current(sums.begin(), sums.end());
    for(int q = 1; q < quantity[c]; ++q)
    {
        for(auto sum : current) 
        {
            sums.insert(sum + q * coins[c]);
        }
    }
}