diff options
author | Christian Grothoff <christian@grothoff.org> | 2021-04-28 00:00:37 +0200 |
---|---|---|
committer | Christian Grothoff <christian@grothoff.org> | 2021-04-28 00:00:37 +0200 |
commit | 2a619eadbe510c49e3b6a29d0813168840da998c (patch) | |
tree | fc9096af1d5ddfef1eaddd222fe84c9fb9b06d22 /contrib/articles/spending.txt | |
parent | 9b89387535cce603f80c9280063ffc7641279143 (diff) | |
download | wallet-core-2a619eadbe510c49e3b6a29d0813168840da998c.tar.xz |
fix more typos
Diffstat (limited to 'contrib/articles/spending.txt')
-rw-r--r-- | contrib/articles/spending.txt | 6 |
1 files changed, 3 insertions, 3 deletions
diff --git a/contrib/articles/spending.txt b/contrib/articles/spending.txt index 3919117bc..7f2c716f8 100644 --- a/contrib/articles/spending.txt +++ b/contrib/articles/spending.txt @@ -67,7 +67,7 @@ Now there are some additional complexities related to giving change and not know 3. Integer linear programming (It helps with understanding the greedy algorithm too) -We almost have an integer linear program because all these functions parameterized by D are simply vectors. We just need to eliminate that annoying max(0, ), which we do by introducing a variable z. I'm going to switch from t[x] to d[x] = t[x] + p[x] and surpress the indexes [x] here since only m, c, and z lack indexes. +We almost have an integer linear program because all these functions parameterized by D are simply vectors. We just need to eliminate that annoying max(0, ), which we do by introducing a variable z. I'm going to switch from t[x] to d[x] = t[x] + p[x] and suppress the indexes [x] here since only m, c, and z lack indexes. Select d : D -> Z and p : D -> Z so as to minimize the function z + sum_x ( r*p + c*(d+p) ) @@ -119,11 +119,11 @@ It's maybe now easier to visualize the greedy algorithm working when you think a 4. Smarter Greed -If we're only allowed to spend one denomination at some price, then we shown the minium is achieved when that denomination x in D is chosen to minimize +If we're only allowed to spend one denomination at some price, then we shown the minimum is achieved when that denomination x in D is chosen to minimize (f[x]+c)/v[x] + (r[x]+c)/(v[x]*d[x])*p[x] where p[x] = max(1,price mod v[x]). We could approximate this by (f[x]+c)/v[x] under several reasonable hypotheses, not unfortunately r >> f, but price >> v[x] still helps. In any case, there are many situations where minimizing (f[x]+c)/v[x] handles this single denomination spend. -We know from our optimal substructure property that, for an optimal allocation, there is a denomination x such that zeroing out t[y], p[y], and v'[y] for y not x, and adjusting the price acordingly, gives an optimal allocation. It follows that a greedy algorithm that uses D sorted by increasing (f[x]+c)/v[x] frequently works, although not when mints charge too much for refreshes +We know from our optimal substructure property that, for an optimal allocation, there is a denomination x such that zeroing out t[y], p[y], and v'[y] for y not x, and adjusting the price accordingly, gives an optimal allocation. It follows that a greedy algorithm that uses D sorted by increasing (f[x]+c)/v[x] frequently works, although not when mints charge too much for refreshes Roughly this algorithm looks like: |