背包问题.ppt

背包问题
有一个贼在偷窃一家商店时发现有n件物品:第i件物品值vi元，重wi 磅，(1≤i≤n)，此处vi 和wi 都是整数。他希望带走的东西越值钱越好，但他的背包中最多只能装下m磅的东西(m为整数)。有两种偷窃方式:
1. 01──背包问题
如果每件物品或被带走或被留下，小偷应该带走哪几件东西?
2. 部分背包问题
如果允许小偷可带走某个物品的一部分，小偷应该带走哪几件东西，每件东西的重量是多少?
.
采用贪心策略来解决部分背包问题:
⑴对每件物品计算其每磅价值vi／wi
⑵按每磅价值单调递减的顺序对物品排序。例如，总共有三件物品和一个背包
开始时对具有每磅价值最大的物品尽量多拿一些。如果拿完了该物品
算法：
begin
⑴读入数据；
⑵计算物品的单位重量价值Ti=vi/wi，并将它们从大到小排序；
⑶依次选择单位价值较大的物品装入背包，直至不能装入；
⑷输出最大价值总和s和装货方案；
end;
后仍可以取一些其他物品时，再取具有每磅价值次大的物品，一直继续下去，直到不能取为止.
.
部分背包问题中，在考虑是否把一件物品加到背包中时，不需要把加入该物品的子问题解与不取该物品的子问题解加以比较。由这种贪心方式所形成的所有子问题是互相独立的。
若对0－1背包问题采取贪心策略，顺序取物品1和2
在0－1背包问题中不应取物品1的原因在于这样无法将背包填满，空余的空间降低了它的每磅价值，因此当我们考虑是否要把一件物品加到背包中时，必须对把加进该物品的子问题的解与不取该物品的子问题的解进行比较。由这种方式形成的子问题导致了许多重迭的子问题。对于这一类虽具有最优化结构性质、但产生的子问题互为重迭的试题，一般采用动态程序设计的方法求解。
最优解取的是物品2和３，没有取物品1。两种包含物品1的可能解都不是最优解
.
01年初4装箱问题：一箱的容量为V(0<V<20000)，同时有n个物品(0<n<30)，每个物品有一个体积(正整数)。要求从n个物品中，任取若干个装入箱内，使剩余空间为最小。
样例：
输入：24　　 {表箱子容量}
　　 　 6　　 {n个物品}
　　 　 8　3　12　7　9　7　　
输出：0　　　 {表箱剩余空间}
i0
1
2
3
4
5
6
t t
t
t
t
t
t
t
t
t
t
t
t
t
t
t
t
t
t
t
t
t
t
t
t
t
t
t
t
t
t
t
t
t
t
t
t
t
t
t
t
t
t
讨论：
阶段？
状态？
决策？
状态转移？
可取的物品有i个
能组成的各种体积
加入i能组成满足条件的体积(取、不取)
f[i]=max{f[j]+w[i] | 取i}
j<i<=n
f[i]=max{f[j] | 不取i}
j<i<=n
t
.
program c2001_4;
var i,k,n,v:integer;
w:array[1..30] of integer;
b:array[0..20000] of 0..1;
begin
readln(v);
readln(n);
for i:=1 to n do read(w[i]);
fillchar(b,sizeof(b),0); b[