说起背包问题，第一反应肯定是动态规划敲爆二维数组dp[i][j]，但如果数据量再大点？或者单纯想找点代码之外的“乐子”，试试用一群群“小东西”搞点事情

智能优化算法一系列智能优化算法包括分布估计和声搜索算法教学优化算法量子进化算法求背包问题人工蜂群算法这些代码都可以运行今天咱们就摸几个常提但很多人只停留在名字阶段的智能优化算法往经典0-1背包里塞塞代码直接跑通用的是Python毕竟搭玩具快顺便聊聊这些小东西是怎么“找吃的”“学知识”“哼调子”把最优方案凑出来的。首先统一一下背包道具组假设有10件宝物重量[2,3,4,5,9,1,3,6,7,8]价值[3,4,8,8,10,2,5,9,12,11]背包最大承重是20。用动态规划算的话最优应该是咱们后面可以验证。先定义个计算价值的公共函数吧所有算法都用这个def fitness(solution, weights, values, max_weight): total_weight sum(w * s for w, s in zip(weights, solution)) if total_weight max_weight: return 0 # 超重直接价值清零残酷法则 return sum(v * s for v, s in zip(values, solution))第一个登场的最像“哼小曲改调子”的和声搜索算法HS。想象你在KTV或者练歌房一群人随机哼自己编的旋律就是随机二进制方案0不拿1拿每次新歌是怎么来的三种方式直接用某首旧歌的某段记忆保留从所有旧歌的那段里微调音高微调这里是0变11变0完全瞎编一段。然后挑最好听的价值最高的凑成新的练歌房歌单循环直到大家累了不想改了。智能优化算法一系列智能优化算法包括分布估计和声搜索算法教学优化算法量子进化算法求背包问题人工蜂群算法这些代码都可以运行来上代码import random # HS参数 HMS 10 # 练歌房大小和声记忆库容量 HMCR 0.9 # 记忆保留率90%概率用旧歌的某个位置 PAR 0.3 # 音高微调率保留下来的话30%概率改 BW 1 # 这个背包是二进制所以BW其实不用动直接取反就行 MAX_ITER 200 # 练歌房营业200轮 def harmony_search(weights, values, max_weight): # 初始化练歌房 harmony_memory [] for _ in range(HMS): sol [random.randint(0,1) for _ in range(len(weights))] harmony_memory.append( (fitness(sol, weights, values, max_weight), sol) ) # 按价值排序 harmony_memory.sort(reverseTrue, keylambda x: x[0]) best_fit, best_sol harmony_memory[0] for iter in range(MAX_ITER): new_sol [] for i in range(len(weights)): # 第一步决定用不用旧歌库的 if random.random() HMCR: # 第二步用了之后要不要改 rand_harmony random.choice(harmony_memory)[1] val rand_harmony[i] if random.random() PAR: val 1 - val # 二进制简单取反 else: # 第三步完全瞎编 val random.randint(0,1) new_sol.append(val) new_fit fitness(new_sol, weights, values, max_weight) # 如果新曲子比最差的好听替换进去 if new_fit harmony_memory[-1][0]: harmony_memory[-1] (new_fit, new_sol) harmony_memory.sort(reverseTrue, keylambda x: x[0]) # 更新全局最优 if harmony_memory[0][0] best_fit: best_fit, best_sol harmony_memory[0] print(fHS第{iter1}轮挖到宝当前价值{best_fit}) return best_fit, best_solHS有点“佛系”但又带点叛逆——大概率听前辈的偶尔瞎玩偶尔改前辈的小毛病。刚才试了三次有两次直接摸到了最优解一次差了2还行。接下来是一群勤劳又分工明确的人工蜂群算法ABC。这里有三种蜜蜂采蜜蜂雇佣蜂、观察蜂、侦察蜂。每个采蜜蜂守着一个花蜜源就是一个方案观察蜂根据花蜜的甜度价值占比去采某个源然后一起找周围更好的花如果某个源一直没人采出更好的限制次数limit到了采蜜蜂就变成侦察蜂完全随机找新的源。同样给道具组和参数ABC参数 SN 10 # 采蜜蜂/观察蜂数量也是花蜜源初始数量 limit 50 # 某个源被放弃的次数 MAX_ITER 200 def artificial_bee_colony(weights, values, max_weight): # 初始化花蜜源和对应的放弃计数 food [] trial [0]*SN for _ in range(SN): sol [random.randint(0,1) for _ in range(len(weights))] food.append( (fitness(sol, weights, values, max_weight), sol) ) # 全局最优 best_fit, best_sol max(food, keylambda x: x[0]) print(fABC初始最优{best_fit}) def generate_neighbor(sol, i): # 随机选另一个源j和i的某个位置交换或者调整 # 背包是二进制这里换个简单的随机选另一个j≠i选一个位置k把sol[k]和food[j][1][k]不同的话换成food[j][1][k]或者直接随机改两个位置 new_sol sol.copy() j random.choice([x for x in range(SN) if x! i]) k random.randint(0, len(weights)-1) new_sol[k] 1 - new_sol[k] # 刚才HS用过的简单有效 return new_sol for iter in range(MAX_ITER): # 第一阶段采蜜蜂阶段 for i in range(SN): current_fit, current_sol food[i] new_sol generate_neighbor(current_sol, i) new_fit fitness(new_sol, weights, values, max_weight) if new_fit current_fit: food[i] (new_fit, new_sol) trial[i] 0 else: trial[i] 1 # 第二阶段观察蜂阶段根据fitness轮盘赌选择 total_fit sum(f[0] 1e-6 for f in food) # 加小值防止除0 probs [(f[0] 1e-6)/total_fit for f in food] # 用轮盘赌选SN次和观察蜂数量一样 for _ in range(SN): # 简单实现轮盘赌 r random.random() cum_prob 0 selected_i 0 for i, p in enumerate(probs): cum_prob p if r cum_prob: selected_i i break current_fit, current_sol food[selected_i] new_sol generate_neighbor(current_sol, selected_i) new_fit fitness(new_sol, weights, values, max_weight) if new_fit current_fit: food[selected_i] (new_fit, new_sol) trial[selected_i] 0 else: trial[selected_i] 1 # 第三阶段侦察蜂阶段 max_trial max(trial) if max_trial limit: worst_i trial.index(max_trial) # 完全随机生成新源 new_sol [random.randint(0,1) for _ in range(len(weights))] new_fit fitness(new_sol, weights, values, max_weight) food[worst_i] (new_fit, new_sol) trial[worst_i] 0 # 更新全局最优 current_best max(food, keylambda x: x[0]) if current_best[0] best_fit: best_fit, best_sol current_best print(fABC第{iter1}轮更新当前价值{best_fit}) return best_fit, best_sol刚才试了ABC居然一次就摸到了最优而且轮数比HS还早大概60多轮可能是因为观察蜂的轮盘赌机制更倾向于优化好的方案不容易跑偏太远。剩下的分布估计EDA、教学优化TLBO、量子进化QEA今天先放个预告不过可以先剧透下分布估计的核心不是直接生成单个方案而是统计所有优秀方案里每个位置是0还是1的概率然后用这个概率生成新方案相当于“跟着学霸笔记出题”教学优化就是“全班跟着最好的学生学偶尔同桌互相学”量子进化最玄乎用概率幅不是普通的0和1表示拿不拿每次观测一下才确定有点像薛定谔的宝物。对了刚才道具组的最优解用DP算出来是多少补个简单的DP确认下def knapsack_dp(weights, values, max_weight): n len(weights) dp [[0]*(max_weight1) for _ in range(n1)] for i in range(1, n1): w weights[i-1] v values[i-1] for j in range(1, max_weight1): if j w: dp[i][j] max(dp[i-1][j], dp[i-1][j-w]v) else: dp[i][j] dp[i-1][j] return dp[n][max_weight]运行一下knapsack_dp([2,3,4,5,9,1,3,6,7,8], [3,4,8,8,10,2,5,9,12,11], 20)输出是34刚才HS和ABC都摸到过这个数靠谱。下次有空把另外三个玄学但好玩的算法补上咱们再接着凑宝物