5.5动态规划求解 0/1背包问题
5.5动态规划求解 0/1背包问题
1.问题描述 背包容量M,n个物品，分别具有效益值P1..Pn,物 品重量w1.wn,从n个物品中，选择若干物品放入 背包，物品要么整件放入背包，要么不放入。怎 样决策可以使装入背包的物品总效益值最大？ 形式化描述： 目标函数： max ∑PX1 1si≤j 约束条件： ∑wX;≤M ≤i≤n x1=0或1，p1>0,w;>0,1≤i≤n 0/1背包问题：KNAP(1,n,M)
形式化描述： 目标函数： 约束条件： 0/1背包问题：KNAP(1,n,M) 1ij i i max p x x 0 1,p 0,w 0,1 i n w x M i i i 1 i n i i = 或 1.问题描述 背包容量M，n个物品，分别具有效益值P1…Pn,物 品重量w1…wn,从n个物品中，选择若干物品放入 背包，物品要么整件放入背包，要么不放入。怎 样决策可以使装入背包的物品总效益值最大？
÷0/1背包问题：M=6,N=3,W=(3,3,4),P=(3,3,5) 贪心法：p3w3>p1w1>p2w2 。贪心解 ∑P=5(0,0,1) ÷最优解是：∑P=6(1,1,0)
❖ 0/1背包问题：M=6,N=3,W=(3,3,4),P=(3,3,5) ❖ 贪心法：p3/w3 > p1/w1 > p2/w2 ❖ 贪心解 ∑P=5（0,0,1） ❖ 最优解是：∑P=6（1,1,0）
·贪心法求解0/1背包问题不一定得到最优解 ÷动态规划求解的问题必须满足最优化原理
❖ 贪心法求解0/1背包问题不一定得到最优解！ ❖ 动态规划求解的问题必须满足最优化原理
2.最优化原理证明 设y1y2,yn是×1，X2,,Xn的0/1值最优序列。 若y1=0,KNAP(2,n,M)是初始决策产生的状态。则 y2yn相对于KNAP(2,n,M)将构成一个最优序列。否则， y1y2,yn将不是KNAP(1,n,M)的最优解 若y1=1,KNAP(2,n,M一w1)是初始决策产生的状态。 则y2yn相对于KNAP(2,n,M一w1)将构成一个最优序列。 否则，设存在另一0/1序列z1,Z2,乙n,使得∑w,2≤M-w 2≤i≤n 且 ∑p,,≥∑py 2≤i≤n 2≤i≤n 则序列y1,z2,,Zn将是一个对于KNAP(1,n,M)具有更大 效益值的序列。 故，最优性原理成立
设y1 ,y2 ,…,yn是x1 ,x2 ,…,xn的0/1值最优序列。 若y1＝0, KNAP(2,n,M)是初始决策产生的状态。则 y2 ,…,yn相对于KNAP(2,n,M)将构成一个最优序列。否则， y1 ,y2 ,…,yn将不是KNAP(1,n,M)的最优解 若y1＝1, KNAP(2,n,M－w1 )是初始决策产生的状态。 则y2 ,…,yn相对于KNAP(2,n,M－w1 )将构成一个最优序列。 否则，设存在另一0/1序列z1 ,z2 ,…,zn ,使得 且 则序列y1 ,z2 ,…,zn将是一个对于KNAP(1,n,M)具有更大 效益值的序列。 故，最优性原理成立 − i n wi zi M w 2 1 i n i n i i i i p z p y 2 2 2.最优化原理证明