P*******b
发帖数: 1001 | 1 从一副牌中选n张，使其和为。
打印所有结果。
要求不能用递归。
谁给讲讲思路吧。谢谢 | s*****n
发帖数: 5488 | 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*******b
发帖数: 1001 | 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**u
发帖数: 10158 | 4 subset sum，动态规划
【在 P*******b 的大作中提到】
: 谢谢回复。再问一下。这里for each collection of cards, 这些collection这么造出
: 来的？
| s*****n
发帖数: 5488 | 5 就是说你可以用任何的collection.arraylist,vector, list 或者whatever java/c#
generic.
【在 P*******b 的大作中提到】
: 谢谢回复。再问一下。这里for each collection of cards, 这些collection这么造出
: 来的？
| P*******b
发帖数: 1001 | 6 container?
看算法好像有好多个container，不太明白怎么来的。
【在 s*****n 的大作中提到】
: 就是说你可以用任何的collection.arraylist,vector, list 或者whatever java/c#
: generic.
| P*******b
发帖数: 1001 | 7 能否给个能抽象成这道题的链接
【在 M**u 的大作中提到】
: subset sum，动态规划
| P********l
发帖数: 452 | 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*******b
发帖数: 1001 | 9 试了一下，能判断是否有满足条件的解，但是不知道怎么把所有的解都出来。
还望多指教。
【在 M**u 的大作中提到】
: subset sum，动态规划
| P*******b
发帖数: 1001 | 10 就是非递归的到所有组合吧。我觉得可以吧，不过看不太懂。
【在 P********l 的大作中提到】
: 这是那个“数组里两个数和为给定值”问题的扩展版。
: 觉得枚举每个组合就挺好。比如，52张牌选三张的组合是
: 1, 1, 1
: 1, 1, 2
: 1, 1, 3
: 。。。
: 1, 1, 13
: 1, 2, 2
: 1, 2, 3
: 。。。
| P*******b
发帖数: 1001 | 11 再贴一下原题
有n张扑克牌，从中随机选出几张。要求找出所有的选法，使得所选扑克牌的点数的和是
s. 不用recursion,代码行数越少越好。
【在 P*******b 的大作中提到】
: 就是非递归的到所有组合吧。我觉得可以吧，不过看不太懂。
|
|
