算法改进 for Unbounded Knapsack

看我这个算法有问题吗？

背包问题传统DP
Example:
Input: W=4
         val = [6,18]
        wt = [2,3]
Output : 18
Input : W = 50
         val = [6,18]
        wt =[2,3]
Output: 594
Below is the implementation of  traditional algorithm.
Python3
def unboundedKnapsack(W, val, wt):
    dp = [0 for i in range(W + 1)]
    for i in range(W + 1):
        for j in range(len(wt)):
            if (wt[j] <= i):
                dp = max(dp[i], dp[i - wt[j]] + val[j])
    return dp[W]
Run time is O(nW) , n is the count of items.
观察与改进：
If we output the dp list  from 0 to 50 for W=50 val =[6,18] wt = [2,3].
[0, 0, 6, 18, 18, 24, 36, 36, 42, 54, 54, 60, 72, 72, 78, 90, 90, 96, 108, 108, 114, 126, 126, 132, 144, 144, 150, 162, 162, 168, 180, 180, 186, 198, 198, 204, 216, 216, 222, 234, 234, 240, 252, 252, 258, 270, 270, 276, 288, 288, 294]
from i>=3 we find dp[i] = dp[i-3] + 18 .  从那开始总在dp[i-3]的基础上拿单位价值最大的。
如果我们发现足够连续(大于单位价值最大的重量)的i都满足以上条件， 那再往后的就可以推算出来.
Below is the implementation of  new algorithm.
Python3
def unboundedKnapsackBetter(W, val, wt):
    #get max dense item index
    maxDenseIndex = 0
    for i in range(1,len(val)):
        if (val[i]*1.0/wt[i]) > (val[maxDenseIndex]*1.0/wt[maxDenseIndex]):
            maxDenseIndex = i
    dp = [0 for i in range(W + 1)]
    counter = 0
    breaked = False
    for i in range(W + 1):
        for j in range(len(wt)):
            if (wt[j] <= i):
                dp[i] = max(dp[i], dp[i - wt[j]] + val[j])
        if i-wt[maxDenseIndex] >=0 and dp[i] - dp[i-wt[maxDenseIndex]] == val[maxDenseIndex]:
            counter +=1
            if counter>=wt[maxDenseIndex]:
                breaked = True
                #print(i)
                break
        else:
            counter = 0
    if not breaked:
        return dp[W]
    else:
        start = i - wt[maxDenseIndex] - 1
        times = (W - start) // wt[maxDenseIndex]
        index = (W - start) % wt[maxDenseIndex] + start
        return (times * val[maxDenseIndex] + dp[index])
If we uncomment the #print(i) in the code, we can see i value when we break the loop.
Test input:
  W = 384
   val = [78, 16, 94 ,36, 87, 93, 50, 22, 63, 28, 91, 60, 64, 27, 41, 27, 73, 37, 12, 69, 68, 30, 83, 31, 63, 24, 68, 36, 30, 3, 23, 59, 70, 68]
   wt = [94 , 57, 12 ,43, 30, 74, 22, 20, 85, 38, 99, 25, 16, 71, 14, 27, 92, 81, 57, 74, 63, 71, 97, 82,  6, 26, 85, 28, 37, 6, 47, 30, 14, 58]
   Output:  4032
the print i value is 11 in this case, that means the run time is (11* 34 ),  while the  traditional algorithm is (W*count of items) = (384*34).
这个情况下如果只是W再变大的话， 时间复杂度也不会变化了。






































[/i][/i][/i][/i][/i][/i][/i]

start = i - wt[maxDenseIndex] - 1 应该是 start = i - wt[maxDenseIndex]

zhang_yi_jun75 发表于 2021-5-23 04:59
start = i - wt[maxDenseIndex] - 1 应该是 start = i - wt[maxDenseIndex]

start = i - wt[maxDenseIndex] - 1 应该是 start = i - wt[maxDenseIndex] + 1