Mercurial > lbo > hg > ccplay

changeset 15:fc43055d41d8

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
DP: coin change, more efficient
author Lewin Bormann <lbo@spheniscida.de>
date Wed, 22 Mar 2023 21:56:20 +0100
parents 3cf1e46d317e
children d6798d2acfb3
files dynprog.cc
diffstat 1 files changed, 6 insertions(+), 8 deletions(-) [+]
line wrap: on
line diff
--- a/dynprog.cc	Wed Mar 22 21:54:12 2023 +0100
+++ b/dynprog.cc	Wed Mar 22 21:56:20 2023 +0100
@@ -5,7 +5,6 @@
 #include <iostream>
 #include <numeric>
 #include <ranges>
-#include <set>
 #include <sstream>
 #include <string>
 #include <tuple>
@@ -315,16 +314,15 @@
 }
 
 // https://www.techiedelight.com/coin-change-problem-find-total-number-ways-get-denomination-coins/
-int coin_change_problem(const vector<int>& coins, int amount_left, vector<int>& current, set<vector<int>>& possibilities) {
+int coin_change_problem(const vector<int>& coins, int amount_left, vector<int>& current, vector<vector<int>>& possibilities) {
     if (amount_left == 0 && !current.empty()) {
-        vector<int> current_{current};
-        sort(current_.begin(), current_.end());
-        possibilities.insert(current_);
+        possibilities.push_back(current);
         return 1;
     } else if (amount_left > 0) {
         int possible_count = 0;
         for (int coin : coins) {
             if (coin > amount_left) continue;
+            if (!current.empty() && coin < *(current.end()-1)) continue;
             current.push_back(coin);
             possible_count += coin_change_problem(coins, amount_left-coin, current, possibilities);
             current.pop_back();
@@ -338,11 +336,11 @@
     vector<int> coins{1, 3, 5, 7};
     int amount = 8;
     vector<int> current{};
-    set<vector<int>> possibilities{};
+    vector<vector<int>> possibilities{};
 
-    int N = timeit_f([&]() -> int { return coin_change_problem(coins, amount, current, possibilities); });
+    int N = timeit_f([&]() -> int {return coin_change_problem(coins, amount, current, possibilities); });
 
-    fmt::print("{}: {}\n", possibilities.size(), possibilities);
+    fmt::print("{}: {}\n", N, possibilities);
 }
 
 int lcss_main(void) {