x********3
发帖数: 160 | 1 有一个排序之后的数组有n个元素，取其中k个元素使得他们的和为sum。问这样的组合
一共有多少种？
例如数组A=[1,2,4,5,7,8],取2个数和为9的一共有3种[1,8],[2,7]和[4,5]。
我的解法是递归。应该有更好的解法吧，因为我没有用到已排序这个特性，而且递归效
率蛮差的。多谢！ | q****x
发帖数: 7404 | 2 2的话很简单。一个头指针，一个尾指针，求和。小，头移动，大，尾移动。相等，同
时移动，直到相遇。
3的话，考虑sum-x[i]，化归为2。
【在 x********3 的大作中提到】
: 有一个排序之后的数组有n个元素，取其中k个元素使得他们的和为sum。问这样的组合
: 一共有多少种？
: 例如数组A=[1,2,4,5,7,8],取2个数和为9的一共有3种[1,8],[2,7]和[4,5]。
: 我的解法是递归。应该有更好的解法吧，因为我没有用到已排序这个特性，而且递归效
: 率蛮差的。多谢！
| x********3
发帖数: 160 | 3 2我只是举个例子，其实是任意的，当然应该远小于数组长度。谢谢！
【在 q****x 的大作中提到】
: 2的话很简单。一个头指针，一个尾指针，求和。小，头移动，大，尾移动。相等，同
: 时移动，直到相遇。
: 3的话，考虑sum-x[i]，化归为2。
| q****x
发帖数: 7404 | 4 任意是NPC吧。什么叫远小于？k = n/100算不算远小于？可k还是O(n)。
【在 x********3 的大作中提到】
: 2我只是举个例子，其实是任意的，当然应该远小于数组长度。谢谢！
| g***s
发帖数: 3811 | 5 DP can solve it number are positive interger and sum is not very large.
【在 x********3 的大作中提到】
: 有一个排序之后的数组有n个元素，取其中k个元素使得他们的和为sum。问这样的组合
: 一共有多少种？
: 例如数组A=[1,2,4,5,7,8],取2个数和为9的一共有3种[1,8],[2,7]和[4,5]。
: 我的解法是递归。应该有更好的解法吧，因为我没有用到已排序这个特性，而且递归效
: 率蛮差的。多谢！
| A**u
发帖数: 2458 | 6 这个题目我刚好练过
这里有介绍
http://www.geeksforgeeks.org/archives/14469
用backtracking.
关键是，这个树的有些node, 可以不用访问
比如 你要找9.
假设从1开始那么，到达(1,2,4)node.
(1,2,4)的和 加上 {5,7,8}的最小值 > 9.
所以不用考虑 包含1，2，4的node了，这样可以可以排序不少点
这是我的算法
#include
#include
#include
using namespace std;
void re(int depth, int sum, vector selected,int w[], int N, int target){
if ( depth == N )
{
if ( sum == target )
{
for(vector::iterator it = selected.begin(); it != selected.
end(); ++it)
cout << *it << " ";
cout << endl;
}
return;
}
re(depth + 1, sum, selected, w, N, target);
selected.push_back(w[depth]);
re(depth + 1, sum + w[depth], selected, w, N, target);
}
void subset_re(int w[], int N, int target ){
vector result;
re(0, 0, result, w, N, target);
}
bool promising(int depth, int sum_so_far, int sum_left, int w[], int N,int
target){
if ( depth < N)
return (sum_so_far + sum_left >= target) && ( sum_so_far == target
|| sum_so_far + w[depth] <= target );
else
return true;
}
void bk(int depth, int sum_so_far, int sum_left, vector selected, int w
[], int N, int target ){
if ( promising(depth,sum_so_far,sum_left,w, N, target) ){
if (sum_so_far == target )
{
for(vector::iterator it = selected.begin(); it != selected.
end(); ++it)
cout << *it << " ";
cout << endl;
}
else{
if (depth < N){
selected.push_back(w[depth]);
bk(depth + 1, sum_so_far + w[depth], sum_left - w[depth],
selected, w, N, target);
selected.pop_back();
bk(depth + 1, sum_so_far, sum_left - w[depth], selected,w, N
, target);
}
}
}
return;
}
void subset_bk(int w[], int N, int target){
vector result;
int all = 0;
for(int i = 0; i < N; ++i)
all += w[i];
bk(0,0,all,result, w, N, target);
}
int main(){
int weights[8] = {15, 22, 14, 26, 32, 9, 16, 8};
int target = 53;
sort(weights,weights + 8);
// for(int i = 0; i < 8; ++i)
// cout << weights[i] << " ";
int w2[3] = {2,4,6};
// subset_re(w2,3,6);
subset_re(weights,8,target);
subset_bk(weights,8,target);
// subset_bk(w2,3,6);
return 0;
}
【在 x********3 的大作中提到】
: 有一个排序之后的数组有n个元素，取其中k个元素使得他们的和为sum。问这样的组合
: 一共有多少种？
: 例如数组A=[1,2,4,5,7,8],取2个数和为9的一共有3种[1,8],[2,7]和[4,5]。
: 我的解法是递归。应该有更好的解法吧，因为我没有用到已排序这个特性，而且递归效
: 率蛮差的。多谢！
|
|
