UC知道pascal高手来看
来源：百度知道 编辑：UC知道 时间：2024/05/27 11:15:36
数字组合
Time Limit:1000MS Memory Limit:65536K
Total Submit:9 Accepted:2
Description
在N个数中找出其和为M的若干个数。先读入正整数N（1〈N〈100）和M（1〈M〈10000）， 再读入N个正数（可以有相同的数字，每个数字均在1000以内）， 在这N个数中找出若干个数， 使它们的和是M， 把满足条件的数字组合都找出来以统计组合的个数，输出组合的个数（不考虑组合是否相同）。要求你的程序运行时间不超过1秒。
Input
第一行是两个数字，表示N和M。
第二行起是N个数。
Output
就一个数字，表示和为M的组合的个数。
Sample Input
4 4
1 1 2 2
Sample Output
3
贴个例程谢谢！
Time Limit:1000MS Memory Limit:65536K
Total Submit:9 Accepted:2
Description
在N个数中找出其和为M的若干个数。先读入正整数N（1〈N〈100）和M（1〈M〈10000）， 再读入N个正数（可以有相同的数字，每个数字均在1000以内）， 在这N个数中找出若干个数， 使它们的和是M， 把满足条件的数字组合都找出来以统计组合的个数，输出组合的个数（不考虑组合是否相同）。要求你的程序运行时间不超过1秒。
Input
第一行是两个数字，表示N和M。
第二行起是N个数。
Output
就一个数字，表示和为M的组合的个数。
Sample Input
4 4
1 1 2 2
Sample Output
3
贴个例程谢谢！
类似0/1背包的思想。经典的动态规划题吧。
记数组f[i,j]表示前i个数字中取若干数字相加和为j的组合数
状态转移f[i,j]=f[i-1,j]+f[i-1,j-a[i]]，分别表示是否取第i个数字a[i]
数组f中除f[0,0]=1外，其余一律赋值为0,表示暂时无法实现。
a[i]表示输入数据中的第i个数字。
数组f定义为f[0..n,0..m]
程序核心部分就是
for i:=1 to n do
for j:=0 to m do
begin
f[i,j]:=f[i-1,j];
if j>=a[i] then f[i,j]:=f[i,j]+f[i-1,j-a[i]];
end;
最后输出f[n,m]就可以了。