请教个题目 - 未名空间MITBBS历史存档

国际科技财经博客移民网络热点娱乐民生时事公众号

Redian新闻

>未名空间

>JobHunting - 待字闺中

请教个题目

请教个题目# JobHunting - 待字闺中

P*b2010-10-22 07:10

1 楼

从一副牌中选n张，使其和为。
打印所有结果。
要求不能用递归。
谁给讲讲思路吧。谢谢

s*n2010-10-22 07:10

2 楼

for number of cards from 1 to 为。, do
for each collection of cards,
if cards number < n,
foreach the rest card c of this collection,
sum = c + sum(collection)
if sum < n, add c union collection into a new collection,
if sum = n, print c union collection,
end foreach
remove the collection from the collection of the collection
end foreach
end for

【在 P*******b 的大作中提到】

: 从一副牌中选n张，使其和为。
: 打印所有结果。
: 要求不能用递归。
: 谁给讲讲思路吧。谢谢

P*b2010-10-22 07:10

3 楼

谢谢回复。再问一下。这里for each collection of cards, 这些collection这么造出
来的？

【在 s*****n 的大作中提到】

: for number of cards from 1 to 为。, do
: for each collection of cards,
: if cards number < n,
: foreach the rest card c of this collection,
: sum = c + sum(collection)
: if sum < n, add c union collection into a new collection,
: if sum = n, print c union collection,
: end foreach
: remove the collection from the collection of the collection
: end foreach

M*u2010-10-22 07:10

4 楼

subset sum，动态规划

【在 P*******b 的大作中提到】

: 谢谢回复。再问一下。这里for each collection of cards, 这些collection这么造出
: 来的？

s*n2010-10-22 07:10

5 楼

就是说你可以用任何的collection.arraylist,vector, list 或者whatever java/c#
generic.

【在 P*******b 的大作中提到】

: 谢谢回复。再问一下。这里for each collection of cards, 这些collection这么造出
: 来的？

P*b2010-10-22 07:10

6 楼

container?
看算法好像有好多个container，不太明白怎么来的。

【在 s*****n 的大作中提到】

: 就是说你可以用任何的collection.arraylist,vector, list 或者whatever java/c#
: generic.

P*b2010-10-22 07:10

7 楼

能否给个能抽象成这道题的链接

【在 M**u 的大作中提到】

: subset sum，动态规划

P*l2010-10-22 07:10

8 楼

这是那个“数组里两个数和为给定值”问题的扩展版。
觉得枚举每个组合就挺好。比如，52张牌选三张的组合是
1, 1, 1
1, 1, 2
1, 1, 3
。。。
1, 1, 13
1, 2, 2
1, 2, 3
。。。
11, 13, 13
12, 12, 12
12, 12, 13
12, 13, 13
13, 13, 13
如果要选4张牌，使其和为28，就可以通过前三张算出第四张，然后检查是否符合要求。
代码：
http://code.google.com/p/sureinterview/source/browse/test/test1/CombinationTest.java#120
public void testNumComb2() {
// list all combinations of c(7,3)
int suit = 4;
int rank = 13;
int takeN = 3; ／／4－1＝3。
int totalNum = 28;
List numList = new ArrayList();
for (int i = 1; i <= rank; i++) {
for (int j = 0; j < suit; j++) {
numList.add(i);
}
}
Combination comb = new CombinationImpl(numList,
takeN);
for (List cb : comb) {
// System.out.println(StringUtils.join(cb.toArray(), ", "));
int sum = 0;
for (Integer num : cb) {
sum += num;
}
int lastNum = totalNum - sum;
int tk1 = cb.get(takeN - 1);
／／检查是否符合要求
if (lastNum <= rank && (lastNum > tk1 || //
((takeN < suit || tk1 == cb.get(takeN - suit)) &&
lastNum == tk1))) {
System.out.print(StringUtils.join(cb.toArray(), ", "));
System.out.println(", " + lastNum);
}
}
}
枚举带重复的组合的代码：
http://code.google.com/p/sureinterview/source/browse/src/lib/combination/CombinationImpl.java#158
看看有问题没有?

P*b2010-10-22 07:10

9 楼

试了一下，能判断是否有满足条件的解，但是不知道怎么把所有的解都出来。
还望多指教。

【在 M**u 的大作中提到】

: subset sum，动态规划

P*b2010-10-22 07:10

10 楼

就是非递归的到所有组合吧。我觉得可以吧，不过看不太懂。

【在 P********l 的大作中提到】

: 这是那个“数组里两个数和为给定值”问题的扩展版。
: 觉得枚举每个组合就挺好。比如，52张牌选三张的组合是
: 1, 1, 1
: 1, 1, 2
: 1, 1, 3
: 。。。
: 1, 1, 13
: 1, 2, 2
: 1, 2, 3
: 。。。

P*b2010-10-22 07:10

11 楼

再贴一下原题
有n张扑克牌，从中随机选出几张。要求找出所有的选法，使得所选扑克牌的点数的和是
s. 不用recursion,代码行数越少越好。

【在 P*******b 的大作中提到】

: 就是非递归的到所有组合吧。我觉得可以吧，不过看不太懂。