B??s(a)，问是否存在A??A，使得?s(a)?a?Aa?A?B。 2{1,2,5,4,6,3,3} 24 t(3,5)=T t(3,9)=F
t(2,4)=F t(7,12)=T?F t(n,B/2)
令t(i,j)表示前i个元素中是否可以取出一部分元素其和为j，即，t(i,j)=T表示前i个元素中可以取出一部分元素其和为j，t(i,j)=F表示前i个元素中不可能取出一部分元素其和为j，则划分问题就是计算 t(n, B/2) 的值。
1 2 i n 0 1 F F T 2 T T T 3 F T T 4 F F T T 0 T T T T T 1 2 T T T j F ? t(i,j) ? B/2 ？？ 1, 2 T 2, 3 T 3, 1 T 4, 2 T
27
?T,?T,??t(i,j)??T,?T,???F,i?1,j?0i?1,j?s(ai)i?1,t(i?1,j)?Ti?1,t(i?1,j?s(ai))?Tothers
3．背包问题
背包问题 n个物品，体积分别为v1，v2，?，vn，价值分别为p1，p2，?，pn，一个容积为V的包，取哪些物品放入包内，使包内物品总价值最高。
??max????s.t.???z=?pixii=1n?vxi=1nii?V
xi=0,1设p1≤p2≤?≤pn，
对i位数组（x1,x2,?,xi），构造有序对
Pi??pjxj,Vi??vjxj，
j?1j?1ii由于（x1,x2,?,xi）有2i种不同的取值，所以对应有2i个不同的有序对，将这些有序对组成集合S(i)，但有两种情况对应的有序对不放入S(i)：
1)Vi>V；
2)两个有序对
28
S(i)构造完成后，如下构造S(i+1)：
1）S(i) ?S(i+1)；
2）｛
4．排工问题
n个工件，每个工件都要按顺序经过A、B两个机床进行加工，工件i在A、B两个机床上加工时间分别为ai，bi，确定n个工件的加工顺序，使得总加工时间最短。
例：
A B N1 4 1 N2 2 3
先加工N1，所需总时间为4＋2＋3＝9，先加工N2，所需总时间为2＋4＋1＝7。
定理 最优加工方案当工件在A、B机床上加工顺序相同时达到（证略）。
状态(X,t)：X中是还没有经过A机床加工的工件，t是B机床加工X外的工件还需要的时间，如果取i?X为下一个放在A上加工的工件，则i在A上完成加工时达到下一个状态(X－i，zi(t))，其
中
29
t?ai?b,zi(t)??i?t?ai?bi,t?ai?max{t?ai,0}?bi ?max{t?ai?bi,bi}ai i X A B t 状态（X，t）
A X－i
bi i Zi(t) 状态（X－i，zi(t)）
B
令f(X,t)为处于状态(X,t)时剩余的最优排工时间，则f(X,t)是t的单调上升函数，且
?f(X,t)?min{ai?f(X?i,zi(t))}i?X??， ??f(?,t)?tf({1,2,?,n},0)即为n个工件的最优加工时间。
在状态(X,t)时对于X中的两个工件i, j，下面讨论应该先加
30
工i还是先加工j才能使得剩余加工时间最少。
如果先加工i，则剩余最优加工时间记为
f(X,t,i)?ai?f(X?i,zi(t))，
如果接着下一个加工j，则最优加工时间为
f(X,t,i,j)?ai?aj?f(X?i?j,zj(zi(t)))，
其中
zj(zi(t))?max{zi(t)?aj,0}?bj?max{zi(t)?aj?bj,bj}?max{max{t?ai?bi,bi}?aj?bj,bj}?max{t?ai?aj?bi?bj,bi?bj?aj,bj}同理，如果状态(X,t)时先加工j，再加工i，则最好加工时间为
f(X,t,j,i)?ai?aj?f(X?i?j,zi(zj(t)))zi(zj(t))?max{t?ai?aj?bi?bj,bi?bj?ai,bi}，
由f(X,t)是t的单调上升函数，要想f(X,t,i,j)?f(X,t,j,i)，只要
zj(zi(t))?zi(zj(t))，
即，
max{t?ai?aj?bi?bj,bi?bj?aj,bj}?max{t?ai?aj?bi?bj,bi?bj?ai,bi}
只需要
31