01背包问题(动态规划法).docx

0/1背包问题1.问题描述给定一个载重量为m,n个物品，其重量为吗，价值为片，1v=iv=n，要求:把物品装入背包，并使包内物品价值最大2.问题分析在0/1背包问题中，物体或者被装入背包，或者不被装入背包，只有两种选择。循环变量i，j意义：前i个物品能够装入载重量为j的背包中(n+1)*(m+1)数组value意义：valueij表示前i个物品能装入载重量为j的背包中物品的最大价值若wij，第i个物品不装入背包否则，若wiv=j且第i个物品装入背包后的价值valuei-1j,贝1记录当前最大价值(替换为第i个物品装入背包后的价值)计算最大价值的动态规划算法如下：/计算for(i=1;ivrow;i+)for(j=1;jvcol;j+)wij,第i个物品不装入背包valueij=valuei-1j;wiv=j,且第i个物品装入背包后的价值valuei-1j,则记录当前最大价值inttemp=valuei-1j-wi+vi