版权声明：本文为博主原创文章，转载请注明转自 

1 #!/usr/bin/env python 2 # -*- coding:utf-8 -*- 3 class bag(): 4     def __init__(self,weight,value): 5         self.weight = weight 6         self.value = value 7     def knapsack(self, full_weight):#weight value存数组 8         result = [[0 for i in range(full_weight+1)] for i in range(len(self.value)+1)] 9         count = len(self.weight)#物品个数10         for n in range(1,count+1):#n当前最大物品个数11             for weight in range(0,full_weight+1):#背包内重量递增12                 if self.weight[n-1]<=weight:#第n个背包的重量为weight[n-1]判断是否小于允许容量13                     if result[n-1][weight]<(result[n-1][weight-self.weight[n-1]]+self.value[n-1]):14                         #如果当前物品在相同重量情况下价值更高15                         result[n][weight]=result[n-1][weight-self.weight[n-1]]+self.value[n-1]16                     else:17                         result[n][weight]=result[n-1][weight]18                 else:19                     result[n][weight] =result[n-1][weight]20         for perrow in result:21             print perrow22         return result23     def find_which(self,full_weight):24         result = self.knapsack(full_weight)25         i= len(result)-126         j = len(result[i])-127         while i >=1:28             while j>=1:29                 if result[i-1][j]!=result[i][j]:#说明当前行的东西拿了30                     print '第'+ str(i)+'个'31                     j = j -self.weight[i-1]32                     i = i - 133                     break34                 else:35                     i = i -136 37 38 def main():39     sort_instance = bag([2,2,6,5,4,1,2,7,5,7,4],[6,3,5,4,6,1,4,7,3,6,1])#重量，价值初始化40     sort_instance.find_which(30)#定义背包总重量41 42 if __name__ =='__main__':43     main()

实现结果：