python 解决0-1背包问题算法,python0-1背包算法,#!/usr/bin/p
文章由Byrx.net分享于2019-03-23 09:03:27
python 解决0-1背包问题算法,python0-1背包算法,#!/usr/bin/p
#!/usr/bin/python# -*- coding: utf8 -*-'''Created on 2011-10-24@author: AHANpython 2.7.2'''#n个物体的重量(w[0]无用)w = [0, 2, 2, 6, 5, 4]#n个物体的价值(p[0]无用)p = [0, 6, 3, 5, 4, 6]#计算n的个数n = len(w) - 1#背包的载重量m = 10#装入背包的物体,元素为True时,对应物体被装入(x[0]无用)x = [False for raw in range(n + 1)]v = 0#optp[i][j]表示在前i个物体中,能够装入载重量为j的背包中的物体的最大价值optp = [[0 for col in range(m + 1)] for raw in range(n + 1)]def knapsack_dynamic(w, p, n, m, x): #计算optp[i][j] for i in range(1, n + 1): for j in range(1, m + 1): optp[i][j] = optp[i - 1][j] if (j >= w[i]) and (optp[i - 1][j - w[i]] + p[i] > optp[i - 1][j]): optp[i][j] = optp[i - 1][j - w[i]] + p[i] #递推装入背包的物体 j = m for i in range(n, 0, -1): if optp[i][j] > optp[i - 1][j]: x[i] = True j = j - w[i] #返回最大价值 v = optp[n][m] return vprint('最大值为:' + str(knapsack_dynamic(w, p, n, m, x)))print(x[1:])
相关内容
- python执行外部程序的四种方法汇总,python四种方法,1、
- python 冒泡,python,[Python]代码#-
- 别再老上网了,上网,[Python]代码#-
- makeNumPwd,,[Python]代码de
- 根据规则生成随机密码,规则生成随机密码,[Python]代码
- 谷歌搜索,,[Python]代码#!
- 统计代码行数,代码行数,TotalLine.py
- Python计算自然周和自然月的首日时间戳,python首日,因工
- python SSH暴力破解工具,pythonssh暴力破解,[Python]代码#!
- 一个用Python给Vim做的插件,PythonVim做插件,function! Go
评论关闭