Pythonダイナミック企画は0-1バックパック問題を解決します.

参考:http://www.tuicool.com/articles/Fji2Qb;このブログの出力で選択したものを間違えました!!!運行環境python 2.x
コードは以下の通りです
璣n-選択する物品の個数に供給して、c-物品の最大の負担(制限条件です)、w-物品ごとの重さ、v-物品ごとの価値

def bag(n,c,w,v):
  res=[[-1 for j in range(c+1)] for i in range(n+1)]
  for j in range(c+1):
    res[0][j]=0
  for i in range(1,n+1):
    for j in range(1,c+1):
      res[i][j]=res[i-1][j]
      if j>=w[i-1] and res[i][j]res[i-1][j]:
       x[i-1]=True
       j-=w[i-1]
  print('      :')
  for i in range(n):
    if x[i]:
      print ' ',i,' ,'
  print('')

if __name__=='__main__':
  n=5
  c=10
  w=[2,2,6,5,4]
  v=[6,3,5,7,6]
  res=bag(n,c,w,v)
  show(n,c,w,res)

  ：[[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0], [-1, 0, 6, 6, 6, 6, 6, 6, 6, 6, 6], [-1, 0, 6, 6, 9, 9, 9, 9, 9, 9, 9], [-1, 0, 6, 6, 9, 9, 9, 9, 11, 11, 14], [-1, 0, 6, 6, 9, 9, 9, 13, 13, 16, 16], [-1, 0, 6, 6, 9, 9, 12, 13, 15, 16, 16]]
     : 16
      :
  0  ,
  1  ,
  3  ,