一个背包问题 pascal

题目啊

求解数还是求解的种类？

解数就f[j]:=f[j]+f[j-k[i]];

解的种类就dfs或者回溯

应该说清楚么，是吧

你就用回溯算法好了，
var a:array[1..1000] of longint;
b:array[1..1000] of boolean;
i,total,n,vmax:longint;
procedure search(k:longint);
var i:longint;
begin
if k=vmax then begin inc(total);exit;end;
if k>vmax then exit;
for i:=1 to n do
if b[i] then begin b[i]:=false;search(k+a[i]);b[i]:=true;end;

end;
begin
fillchar(b,sizeof(b),true);
readln(n,vmax);
for i:=1 to n do
read(a[i]);
search(0);
writeln(total);
end.

今天难得心情好，就稍微打了下，如果溢出就把数组调大一点，你再试试

我来贴题目吧，其实我也不会这道题，我还在另一个帖给人贴了个既超时又超内存的dp，感觉好瞎。

OI练习题：神秘礼物
（题目名：gift）
题目描述：
Pxoylngx有n个想送给G4的礼物，其中第i个送去后G4的高兴度为Ai，现在pxoylngx想从中挑出k个（不能重复），希望G4的高兴度之和恰为19920726（什么意思？自己猜）。Pxoylngx希望k尽可能大，可是，k最大是多少呢？
输入文件（gift.in）：
第一行：一个整数n。
以下n行，每行一个正整数（在longint范围内），为Ai。
输出文件（gift.out）：
一个整数，k的最大值。
如不能使G4的高兴度和为19920726（不是吧~），则输出0。
输入样例1：
4
1
19920720
2
2
输出样例1：
0
输入样例2：
5
19920725
1
19920722
2
2
输出样例2：
3
说明：19920722+2+2=19920726
时限为每个点1秒 空间512MB
对于50%数据，有2<=n<=10。
对于100%数据，有2<=n<=30。

题解是：

Gift的做法：把数组分成前后两半，分别计算前后两半的可取值（不会超时的，O(2^15)），把右边可取值排序（O(log(2^15)*2^15)=O(15*2^15)，再枚举左边的可取值，二分查找就可以了