Dynamic programming

# coding: utf-8 # In[2]: # 动态规划 0/1背包问题 # 参考http://www.hawstein.com/posts/dp-knapsack.html import numpy as np # In[3]: # 一共五个宝石，袋子一共可以放10磅宝石 n=5 c=10 # v代表宝石的重量，w代表宝石的价值 v={0:2,1:2,2:6,3:5,4:4} w={0:6,1:3,2:5,3:4,4:6} # d[i][j]表示在j磅的容量下放i个宝石产生的最大价值 # d=getMatrix(100,100) d=np.zeros([n+1,c+1]) # In[4]: get_ipython().magic('pdb on') # In[19]: for i in range(n+1): for j in range(c+1): if i!=0: d[i][j]=d[i-1][j] # 如果第i-1个宝石没有放进去，那么就是求在j磅的袋里i-1宝石最大的价值 if (i>0): if (j>=v[i-1]): if d[i][j]<(d[i-1][j-v[i-1]]+w[i-1]): d[i][j]=d[i-1][j-v[i-1]]+w[i-1] print('最大能获得的宝石价值为:',d[n][c]) # In[20]: label=np.zeros([n]) # 查看哪些宝石被装进了袋子 for i in range(n,0,-1): if i-1>=0: if d[i][j]>d[i-1][j]: label[i-1]=1 j=j-v[i-1] #//装入第i-1个宝石后背包能装入的体积就只剩下j - V[i-1] print(label) # In[ ]: print(1!=1)

Reference: http://www.hawstein.com/posts/dp-knapsack.html