求一个算法，是对数组进行操作的。
一个二维数组（假设下标从1开始），每个元素的值非0即1。
现要从那些值是1的元素中找出n个元素，使得n个元素的列值之和为S。同时，这n个元素的行值不能重复，也就是说，一行最多只能选一个。
比如：
1 0 0 1
0 1 1 0
1 0 0 1
n=2，S=5
这里面有两组解：a[1][1]、a[3][4]和a[1][4]、a[3][1]
我只要一组就够了，不需要全部的解。但是要能判断出有无解
最后返回的结果只要知道列值，也就是1和4
请高手给个算法，分数嘛不是问题，给多少都没有问题。
问题点数：100、回复次数：6Top
1 楼ywqzxj（午青）回复于 2003-12-04 13:10:15 得分 10
简单搜索加一些剪枝判断就可以了，问一下数组的维数有没有大致范围？Top
2 楼huhuhu5（）回复于 2003-12-04 13:27:30 得分 10
用回溯把1
参考下 八皇后问题
具体的 不用说了吧！Top
3 楼efei（爱琴海）回复于 2003-12-04 13:28:24 得分 0
就是二维的。Top
4 楼ZhangYv（迎着朝阳,走向地狱）回复于 2003-12-04 13:40:44 得分 80
不用那么麻烦。找出矩阵中所有为1的元素，标为二元组<i,j> = 1
如果有K个这样的二元组存在，要求找出其和为S的集合，就是取一个组合数：
C(K,S) 如果K >＝ S则有解Top
5 楼ZhangYv（迎着朝阳,走向地狱）回复于 2003-12-04 13:43:18 得分 0
列值之和为S。同时，这n个元素的行值不能重复...就是生成时候再加以判断是否满足这个约束Top
6 楼efei（爱琴海）回复于 2003-12-04 20:08:45 得分 0
没有人回答我，我自己凑啊凑啊，嘿嘿，凑出来了
Sub Assign(ByVal s As Integer, ByVal n As Integer, a() As Integer)
Dim i As Integer '用来记录intArr()的当前元素
Dim j As Integer '用来记录二维数组当前的行数
Dim k As Integer '在一行内搜索时用来记录列值
Dim intArr() As Integer '存放分配好的分数的数组，二维的
Dim blnIsDown As Boolean '是否在往下搜索
Dim intTopRow As Integer
'初识化变量
blnIsDown = True '一开始是往下搜索的
intTopRow = 0
ReDim intArr(n - 1, 1) As Integer
i = 0: j = 0
'开始探索
Do Until i = n
k = 0
Do Until a(j, k) = 1 And k + 1 <= s '循环找到本行第一个能取的元素
k = k + 1
If k > UBound(a, 2) Then
Exit Do
End If
Loop
If k <= UBound(a, 2) Then '判断是否找到
'找到
blnIsDown = True
intArr(i, 0) = k + 1 '记录列值（分数）
intArr(i, 1) = j '记录行值，为后面的回溯做准备
a(j, k) = -1 '置成-1，表示这个元素已经遍历过了。同时不把它置0是因为回溯时要恢复
s = s - k - 1 '剩下的总分相应地减少
i = i + 1 '指向下一个元素
If s = 0 And i <> n Then
'用的过多，再在本行之内搜索
i = i - 1
intArr(i, 0) = 0
s = s + k + 1
ElseIf i = n And s <> 0 Then
'分用少了，剩下好多
i = i - 1
intArr(i, 0) = 0
s = s + k + 1
Else
j = j + 1
End If
Else
'本行已经空了，要往回回溯
If blnIsDown = False Or j = UBound(a) Then
If j = intTopRow Then
'说明已经回溯到头了，这个时候要下到第二行
j = j + 1
intTopRow = intTopRow + 1
Else
For k = 0 To UBound(a, 2)
a(j, k) = Abs(a(j, k))
Next
If intArr(i - 1, 1) = j - 1 Then
i = i - 1 '退到上一个
s = s + intArr(i, 0) '这个如果是在上一行吃的，则要退回，否则不退
intArr(i, 0) = 0 '把上一个的清空
End If
If j = UBound(a) Then
blnIsDown = False
End If
j = j - 1
End If
Else
j = j + 1
End If
End If
Loop
End SubTop
