動(dòng)態(tài)規(guī)劃之01背包問題及改進(jìn)-文庫(kù)吧資料
2024-08-04 00:49本頁(yè)面
【正文】 ):16 divide = min(weight[i], capacity)17 for j in range(divide):18 result[i].append(result[i + 1][j])19 for j in range(divide, capacity + 1):20 result[i].append(max(result[i + 1][j], result[i + 1][j weight[i]] + value[i]))21 22 result[0] = {capacity: result[1][capacity]}23 if weight[0] = capacity:24 result[0][capacity] = max(result[1][capacity], result[1][capacity weight[0]] + value[0])25 26 vector = [0 for x in range(obj_num)]27 capacity_temp = capacity28 for i in range(obj_num 1):29 if result[i][capacity_temp] != result[i + 1][capacity_temp]:30 vector[i] = 131 capacity_temp = weight[i]32 33 if capacity_temp == 0:34 vector[1] = 035 else:36 vector[1] = 137 38 return {39。該算法的python代碼實(shí)現(xiàn)： 1 01背包問題 2 __author__ = 39。} 取上述二者的最大值，即m(i,j) = max{ 若不放入物品i，則此時(shí)m(i,j)=m(i+1,j) 若放入物品i，此時(shí)背包剩余容量為 jw[i]，在子結(jié)構(gòu)中已求出當(dāng)容量k=0,1,2……C 時(shí)的最優(yōu)值m(i+1,k)。w[i] = jw[i] j對(duì)于此時(shí)背包剩余容量要求原問題的解m(1，C)，可從m(n，C)，m(n1，C)，m(n2，C
黨政相關(guān)相關(guān)推薦
鄂ICP備17016276號(hào)-1