algorithm - Maximum Coin Partition -
since standing @ point of sale in supermarket yesterday, once more trying heuristically find optimal partition of coins while trying ignore impatient , nervous queue behind me, i've been pondering underlying algorithmic problem:
given coin system values v1,...,vn, limited stock of coins a1,...,an , sum s need pay. we're looking algorithm calculate partition x1,...,xn (with 0<=xi<=ai) x1*v1+x2*v2+...+xn*vn >= s such sum x1+...+xn - r(r) maximized, r change, i.e. r = x1*v1+x2*v2+...+xn*vn - s , r(r) number of coins returned cashier. assume cashier has unlimited amount of coins , gives minimal number of coins (by example using greedy-algorithm explained in schoening et al.). need make sure there's no money changing, best solution not give of money (because solution optimal in case).
thanks creative input!
if understand correctly, variant of subset sum. if assume have 1 of each coin (a[i] = 1 each i), solve this:
sum[0] = true = 1 n j = maxsum downto v[i] sum[j] |= sum[j - v[i]] then find first k >= s , sum[k] true. can actual coins used keeping track of coin contributed each sum[j]. closest can sum s using coins, less change be, you're after.
now don't have 1 of each coin i, have a[i] of each coin i. suggest this:
sum[0] = true = 1 n j = maxsum downto v[i] k = 1 a[i] if j - k*v[i] >= 0 sum[j] |= sum[j - k*v[i]] <- use coin k times it should easy x vector this. let me know if need more details.
Comments
Post a Comment