i****t
发帖数: 36 | 1 写一个方法，接受4个整数输入，输出一个integer result.
输入值都介于1至10, 此方法应该返回输入数和值为18的组合数目
例如：输入W, X, Y, and Z, 值为4, 6, 8, 10。输出应该为2
因为和值为18的组合有两个:
Input:
W = 4
X = 6
Y = 8
Z = 10
Combos:
Y + Z = 18
W + X + Y = 18
扩展:
如何改进你的算法以接收随意数目的输入。（不局限于刚好4个输入） | s*********t
发帖数: 1663 | 2 感觉和那个找两个数和为X的题很接近
【在 i****t 的大作中提到】
: 写一个方法，接受4个整数输入，输出一个integer result.
: 输入值都介于1至10, 此方法应该返回输入数和值为18的组合数目
: 例如：输入W, X, Y, and Z, 值为4, 6, 8, 10。输出应该为2
: 因为和值为18的组合有两个:
:
: Input:
: W = 4
: X = 6
: Y = 8
: Z = 10
| M********5
发帖数: 715 | 3 题目没有说完整
数字是1至？
这一题好像也不是那么难。。。。。 | i****t
发帖数: 36 | 4 输入是介于1至10. 能否给点详细的思路？尤其是第二问？？ | M********5
发帖数: 715 | 5 第二问的感觉有点像dynamic programming
要再想想 | l*******g
发帖数: 4894 | 6 I agree.
【在 s*********t 的大作中提到】
: 感觉和那个找两个数和为X的题很接近
| s*********t
发帖数: 1663 | 7 def findsum(arr, s):
ht = {}
for i in arr:
for j in ht.items():
if ht.has_key(j[0]+i):
ht[j[0]+i] += j[1]
else:
ht[j[0]+i] = 1
if ht.has_key(i):
ht[i] += 1
else:
ht[i] = 1
return ht[s]
【在 i****t 的大作中提到】
: 写一个方法，接受4个整数输入，输出一个integer result.
: 输入值都介于1至10, 此方法应该返回输入数和值为18的组合数目
: 例如：输入W, X, Y, and Z, 值为4, 6, 8, 10。输出应该为2
: 因为和值为18的组合有两个:
:
: Input:
: W = 4
: X = 6
: Y = 8
: Z = 10
| c*r
发帖数: 278 | 8 This is not an optimization problem.
【在 M********5 的大作中提到】
: 第二问的感觉有点像dynamic programming
: 要再想想
| l*******g
发帖数: 4894 | 9 your code confuses me. hehe. Sorry.
【在 s*********t 的大作中提到】
: def findsum(arr, s):
: ht = {}
: for i in arr:
: for j in ht.items():
: if ht.has_key(j[0]+i):
: ht[j[0]+i] += j[1]
: else:
: ht[j[0]+i] = 1
: if ht.has_key(i):
: ht[i] += 1
| s*********t
发帖数: 1663 | 10 我也没仔细测试，可能有错
【在 l*******g 的大作中提到】
: your code confuses me. hehe. Sorry.
| | | p******n
发帖数: 32 | 11 What about this solution
S(n, k) = S(n - 1, k) + S(n-1, k-a[n])
n is the number of the input numbers
k is the given sum.
In the case that n = 4, k = 18
S(4, 18) = S(3, 18) + S(3, 8)
S(3, 18) = S(2, 18) + S(2, 10)
S(3, 8) = S(2, 8) + S(2, 0)
among the above, S(2, 10) = 1, S(2, 0) = 1(because a[3] = 8)
Therefore, S(4, 18) = 2 | f*********5
发帖数: 576 | 12 u will get duplicate results.
for example int a[3]={2,1,3};
s(3,3)=s(2,3)+s(2,1)
s(2,1)=1 //only 1,then your combination is 1,2
s(2,3)=s(1,3)+s(1,2)
you will get two combination 3 and 2,1
【在 p******n 的大作中提到】
: What about this solution
: S(n, k) = S(n - 1, k) + S(n-1, k-a[n])
: n is the number of the input numbers
: k is the given sum.
: In the case that n = 4, k = 18
: S(4, 18) = S(3, 18) + S(3, 8)
: S(3, 18) = S(2, 18) + S(2, 10)
: S(3, 8) = S(2, 8) + S(2, 0)
: among the above, S(2, 10) = 1, S(2, 0) = 1(because a[3] = 8)
: Therefore, S(4, 18) = 2
| f*********5
发帖数: 576 | 13 find the combination of items in input[] with the sum of tartget.
static int count=0;
quicksort(input,0,size-1);
void GetCombinationNumber(int input[],int used[],vector&vec,int
size,int target,int *count)
{
if (target==0) { *count++; return; }
for(int i=0;i
{
if (used[i]==1)continue; //we donot want to use them
repeatedly
if ((vec.size()>0)&&(vec.back()>a[i])) continue; //we will use
the items in
order so that we can avoid duplicate
if (t
【在 i****t 的大作中提到】
: 写一个方法，接受4个整数输入，输出一个integer result.
: 输入值都介于1至10, 此方法应该返回输入数和值为18的组合数目
: 例如：输入W, X, Y, and Z, 值为4, 6, 8, 10。输出应该为2
: 因为和值为18的组合有两个:
:
: Input:
: W = 4
: X = 6
: Y = 8
: Z = 10
| i***1
发帖数: 95 | 14 if (the number of element is less than around 20), we can enumerate all
posibilities using bits related method.
else {
//DP. suppose there are N positive numbers V[1] to V[N] and we need to
reach sum S
Possiblity[S,N] stores the final answer
And Possiblity[A,B] stores the number of possibility to sum to A using
the first B numbers
Possiblity[A,B] = possiblity[A-V[B],B-1] + possibility[A,B-1]
} | f*********5
发帖数: 576 | 15 i think u will get duplicate results
need to
using
【在 i***1 的大作中提到】
: if (the number of element is less than around 20), we can enumerate all
: posibilities using bits related method.
: else {
: //DP. suppose there are N positive numbers V[1] to V[N] and we need to
: reach sum S
: Possiblity[S,N] stores the final answer
: And Possiblity[A,B] stores the number of possibility to sum to A using
: the first B numbers
: Possiblity[A,B] = possiblity[A-V[B],B-1] + possibility[A,B-1]
: }
| i***1
发帖数: 95 | 16 Good catch. If there are duplicate numbers in input, and they don't
distinguish from each other, (I mean A=4, B=4, and we don't care variable
name) then both of my methods will get duplicates.
The DP need some changes to address this situation.
【在 f*********5 的大作中提到】
: i think u will get duplicate results
:
: need to
: using
| f*********5
发帖数: 576 | 17 i didn't mean duplicate input,
i mean...
see my above post
variable
【在 i***1 的大作中提到】
: Good catch. If there are duplicate numbers in input, and they don't
: distinguish from each other, (I mean A=4, B=4, and we don't care variable
: name) then both of my methods will get duplicates.
: The DP need some changes to address this situation.
| i*****e
发帖数: 113 | 18 没有重复
可以想象成二叉树，从左到右递归
4--6--8--10
\/ \/ \/
/\ /\ /\
0--0--0--0
从左到右递归
#!/usr/bin/env runhaskell
count [] 0 = 1
count [] _ = 0
count a s = count (tail a) s + count (tail a) (s - head a)
main = print(count [4, 6, 8, 10] 18) | h**6
发帖数: 4160 | 19 既然输入都在1~10之间，用brute force就可以解决了，一共2^10 = 1024种情况 | p******n
发帖数: 32 | 20 这个应该是
s(3, 3) = s(2, 3) + s(2, 0)/* s(2, 0) is 1, because a[3] is 3*/
s(2, 3) = s(1, 3) + s(1, 2)
s(1, 3) = 0
s(1, 2) = 1 /* because a[1] = 2 */
所以 s(3, 3) = 2， 也就是找到两个组合sum up to 3
【在 f*********5 的大作中提到】
: u will get duplicate results.
: for example int a[3]={2,1,3};
: s(3,3)=s(2,3)+s(2,1)
: s(2,1)=1 //only 1,then your combination is 1,2
: s(2,3)=s(1,3)+s(1,2)
: you will get two combination 3 and 2,1
|
|
