Feb 2017
1 / 2
Feb 2017
Feb 2017
vladimira
Feb '17
1

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.

  • created

    Feb '17

  • last reply

    Feb '17
  • 1

    reply

  • 719

    views

  • 1

    user

vladimira
Feb '17

About sorting by quality. Its done correctly. If you want to be sure about where mistake could be, here is code for that part:

v_w = []
for _ in xrange(n):
    v = Read_Next_Int_From_Input()
    w = Read_Next_Int_From_Input()
    v_w.append((v,w))
v_w.sort(cmp = My_Cmp)
    
values = [tpl[0] for tpl in v_w]
weights = [tpl[1] for tpl in v_w]

def My_Cmp(tpl_1, tpl_2):
    v1,w1 = tpl_1
    v2,w2 = tpl_2
    x = v1*w2
    y = v2*w1
    
    if x < y:
        return -1
    if x > y:
        return 1
    if w1 > w2:
        return -1
    else:
        return 1