Hello guys. I ask you to think why this approach gives WA when dp knapsack works.
The idea of algo: create arrays , of coins. Than sort them by "quality" in ascending order.
Quality = value / weight.
Than we try to fill free weight of piggy-bank in the most efficient way, which is to fill it with coins of the minimum quality. Less quality means less value of piggy-bank.
We achieve it so: create vector of coefficients -> a
a[i] = number of coins numerated as i.
We initiate it this way:
W_free = W
a[0] = W_free // weight[0]
W_free -= a[0]*weight[0]
a[1] = W_free // weight[1]
W_free -= a[1]*weight[1]
and so on...
W means weight of piggy bank we want to fill at the begining. W = F - E in terms of the problem's author
If after init stage W_free = 0 we achieved our goal.
Else we decrease a[n-2] (a[n-1] is last element) and fill piggy-bank with more (n-1) coins. And so on. Its clearly the task of lexicographic search.
Here you may see my code for solving part of script. You should notice that cases W=0 and n=1 are checked first. If there is no solution function returns None.
def Solve(W,n,values,weights):
if W == 0:
return 0
if n == 1:
if W % weights[0] == 0:
return values[0] * (W//weights[0])
return None
#====================================
#----------- init a -----------------
a = []
W_free = W
for i in xrange(n):
a.append( W_free // weights[i] )
W_free %= weights[i]
#=================================================
while W_free > 0:
change_i = n - 2
while change_i >= 0 and a[change_i] == 0:
change_i -= 1
if change_i == -1:
break
W_free = W
for i in xrange(change_i + 1):
W_free -= a[i] * weights[i]
# lexicographic down step
a[change_i] -= 1
W_free += weights[change_i]
# filling right part of a vector
for i in xrange(change_i + 1, n):
a[i] = W_free // weights[i]
W_free %= weights[i]
#=================================================
if W_free == 0:
ans = 0
for i in xrange(n):
ans += values[i]*a[i]
return ans
# W_free != 0
# still one combination could be feasible
if W % weights[-1] == 0:
return values[-1] * (W // weights[-1])
else:
return None
PS: sorry if a lot of mistakes in text, I'm not native speaker.