背包最优解计数与背包最优解方案
我们有的时候会遇上求背包最优解有多少种。
记得我们在计算用只有代价的物品凑出固定代价m时的做法吗？我们采用背包的思想：
F[0]:=1;
for i:=1 to n do
for j:=Cost[i] to m do//完全背包
inc(F[j],F[j-Cost[i]]);
当然这是没有价值的物品。
另一种问题完全不同。
在物品有价值的时候，我们可以用背包求出最优解。如果我们要求出最优解有多少种应该怎么做呢？
我们用一个数组Num[j]表示代价为j最优解的方案数。
在F可以更新的时候，Num自然被覆盖：
if F[j]>F[j-Cost[i]]+Value[i] then
begin
F[j]:=F[j-Cost[i]]+Value[i];
Num[j]:=Num[j-Cost[i]];
end;
在F数组遇上相等的数的时候，累加即可。
if F[j]=F[j-Cost[i]]+Value[i] then inc(Num[j],Num[j-Cost[i]]);
初始的时候，Num[i]=1。它的意义在于最初的时候所有代价的最大价值为0，方案数为1。
那么如果我们需要找到最优解的方案呢？
如果我们知道这个物品是否用来更新了，就不难知道方案数了。
于是我们想到用一个Used[i,j]来记录第i个物品是否更新了代价为j的最大价值。
if F[j]<F[j-Cost[i]]+Value[i] then Used[i,j]:=true
如果我们仅仅在“<”的时候更新，“=”的时候不更新，那么我们得到的就是字典序最小的方案（顺序枚举）。
那么我们查找到方案呢？
先令j=m，i=n。考虑从F[j]开始找。如果F[i,j]=true，那么这个物品就是用到更新了，那么把i扔入栈中，i减去1，j减去Cost[i]。
否则说明i没有被用到更新，我们只需i减去1即可。
i:=n;
j:=x;
top:=0;
while i<>0 do
begin
if Used[i,j] then
begin
inc(top);
Stk[top]:=i;
dec(j,Cost[i]);
end;
dec(i);
end;