h*****g 发帖数: 312 | 1 number of combination of integers between 1 and 10, that sum to 15
Problem:
Write a function that takes an array of five integers, each of which is
between 1 and 10,
and returns the number of combination of those integers that sum to 15....
For example, calling the function with the array [1, 2, 3, 4, 5] should
return 1,
while calling it with [5, 5, 10, 2, 3] should return 4
(5 + 10, 5 + 10, 5 + 5 + 2 + 3, 10 + 2 + 3). |
g**********y 发帖数: 14569 | 2 对,这个是标准的DP,就是计算“和空间”。
【在 h*****g 的大作中提到】 : number of combination of integers between 1 and 10, that sum to 15 : Problem: : Write a function that takes an array of five integers, each of which is : between 1 and 10, : and returns the number of combination of those integers that sum to 15.... : For example, calling the function with the array [1, 2, 3, 4, 5] should : return 1, : while calling it with [5, 5, 10, 2, 3] should return 4 : (5 + 10, 5 + 10, 5 + 5 + 2 + 3, 10 + 2 + 3).
|
l*********8 发帖数: 4642 | 3 看起来像背包问题的变种
【在 h*****g 的大作中提到】 : number of combination of integers between 1 and 10, that sum to 15 : Problem: : Write a function that takes an array of five integers, each of which is : between 1 and 10, : and returns the number of combination of those integers that sum to 15.... : For example, calling the function with the array [1, 2, 3, 4, 5] should : return 1, : while calling it with [5, 5, 10, 2, 3] should return 4 : (5 + 10, 5 + 10, 5 + 5 + 2 + 3, 10 + 2 + 3).
|
l*****a 发帖数: 14598 | 4 不会DP
就用求组合的常规办法吧
qsort(a,0,size-1);
void getCombination(int a[],int size,int target,int start,vector&vec)
{
if(target==0) { ... return;}
for(int i=start;i
{
if(a[i]
vec.push_back(a[i]);
if(i
vec.pop_back();
}
}
【在 h*****g 的大作中提到】 : number of combination of integers between 1 and 10, that sum to 15 : Problem: : Write a function that takes an array of five integers, each of which is : between 1 and 10, : and returns the number of combination of those integers that sum to 15.... : For example, calling the function with the array [1, 2, 3, 4, 5] should : return 1, : while calling it with [5, 5, 10, 2, 3] should return 4 : (5 + 10, 5 + 10, 5 + 5 + 2 + 3, 10 + 2 + 3).
|
p*****2 发帖数: 21240 | 5
这时啥意思?
【在 g**********y 的大作中提到】 : 对,这个是标准的DP,就是计算“和空间”。
|
p*****2 发帖数: 21240 | 6
为什么呀?
【在 l*********8 的大作中提到】 : 看起来像背包问题的变种
|
p*****2 发帖数: 21240 | |
p*****2 发帖数: 21240 | 8
能不能以后都写C#code呢?你自己也练习一下,我看着也容易一些。
【在 l*****a 的大作中提到】 : 不会DP : 就用求组合的常规办法吧 : qsort(a,0,size-1); : void getCombination(int a[],int size,int target,int start,vector&vec) : { : if(target==0) { ... return;} : for(int i=start;i: { : if(a[i]: vec.push_back(a[i]);
|
l*********8 发帖数: 4642 | 9 经典背包要求物品的总体积小于等于某个值。 这个问题要求“物品总体积”等于某个值
【在 p*****2 的大作中提到】 : : 能不能以后都写C#code呢?你自己也练习一下,我看着也容易一些。
|
p*****2 发帖数: 21240 | 10
个值
我在wiki看看。
【在 l*********8 的大作中提到】 : 经典背包要求物品的总体积小于等于某个值。 这个问题要求“物品总体积”等于某个值
|
|
|
l*****a 发帖数: 14598 | 11 除了这个vector别的跟C#长的也没什么区别吧
我就怕一会写这个,议会写那个,都混淆了
哪个也写不好
【在 p*****2 的大作中提到】 : : 个值 : 我在wiki看看。
|
p*****2 发帖数: 21240 | 12
个值
背包问题是求最优解。这个是一个组合问题呀。就是看那种组合满足条件就可以了。没
什么dp的关系呀,感觉。
【在 l*********8 的大作中提到】 : 经典背包要求物品的总体积小于等于某个值。 这个问题要求“物品总体积”等于某个值
|
p*****2 发帖数: 21240 | 13
但是你不是已经要转C#了吗?正好算做练习。
【在 l*****a 的大作中提到】 : 除了这个vector别的跟C#长的也没什么区别吧 : 我就怕一会写这个,议会写那个,都混淆了 : 哪个也写不好
|
l*********8 发帖数: 4642 | 14 求最优解: 每个子问题都保存最优解
求组合数: 每个子问题都保存组合数
【在 p*****2 的大作中提到】 : : 但是你不是已经要转C#了吗?正好算做练习。
|
p*****2 发帖数: 21240 | 15
你写个dp公式出来看看。按你的理解应该不难吧。
【在 l*********8 的大作中提到】 : 求最优解: 每个子问题都保存最优解 : 求组合数: 每个子问题都保存组合数
|
Z*****Z 发帖数: 723 | 16 应该是回溯+剪枝吧
【在 h*****g 的大作中提到】 : number of combination of integers between 1 and 10, that sum to 15 : Problem: : Write a function that takes an array of five integers, each of which is : between 1 and 10, : and returns the number of combination of those integers that sum to 15.... : For example, calling the function with the array [1, 2, 3, 4, 5] should : return 1, : while calling it with [5, 5, 10, 2, 3] should return 4 : (5 + 10, 5 + 10, 5 + 5 + 2 + 3, 10 + 2 + 3).
|
S******t 发帖数: 151 | 17 何必高射炮打蚊子,都说的很清楚了, array of five integers..
直接
int cnt=0;
for(int i=0;i<(1<<5);i++) {
int sum = 0;
for(int j=0;j<5;j++)
if(i&(1<
sum+=a[j];
if(sum==15) cnt++;
}
printf("%d\n",cnt);
【在 h*****g 的大作中提到】 : number of combination of integers between 1 and 10, that sum to 15 : Problem: : Write a function that takes an array of five integers, each of which is : between 1 and 10, : and returns the number of combination of those integers that sum to 15.... : For example, calling the function with the array [1, 2, 3, 4, 5] should : return 1, : while calling it with [5, 5, 10, 2, 3] should return 4 : (5 + 10, 5 + 10, 5 + 5 + 2 + 3, 10 + 2 + 3).
|
l*****a 发帖数: 14598 | 18 who told u array of 5?
【在 S******t 的大作中提到】 : 何必高射炮打蚊子,都说的很清楚了, array of five integers.. : 直接 : int cnt=0; : for(int i=0;i<(1<<5);i++) { : int sum = 0; : for(int j=0;j<5;j++) : if(i&(1<: sum+=a[j]; : if(sum==15) cnt++; : }
|
e*****e 发帖数: 1275 | 19 题目好像没有说清楚。
那个数字可以用几次?用一次,和可以用无数次(就是classic coin question)还是有
点区别的哦。~~~~ |
l*********8 发帖数: 4642 | 20 出现几次就可以用几次。
【在 e*****e 的大作中提到】 : 题目好像没有说清楚。 : 那个数字可以用几次?用一次,和可以用无数次(就是classic coin question)还是有 : 点区别的哦。~~~~
|
|
|
l*****a 发帖数: 14598 | 21 或者说,每个只能用一次
【在 l*********8 的大作中提到】 : 出现几次就可以用几次。
|
p*****2 发帖数: 21240 | 22
对。不然就是DP了。
【在 l*****a 的大作中提到】 : 或者说,每个只能用一次
|
l*********8 发帖数: 4642 | 23 (刚写错了一点儿,改了一下)
First, let's look at the situation when no repeated numbers in the
array.
Problem:
Given array A that has n unique positive integers, find the count of
the combinations that have sum m; 0
int S[n][m+1];
S[i][j]: 取出的数字最大下标为i, 而且这些数字求和为j的combination count
S[i][0] = 0; (后来发现这是没有用的, 如果想省空间,可以用S[*][j]存储求和必须为
j+1的count)
S[0][j] = 0 when j not equal to A[0];
S[0][A[0]] = 1
if A[i]>j
S[i][j] = 0;
else if A[i] == j
S[i][j] = 1;
else
S[i][j] = sum (S[k][j-A[j]] | when k = 0...i-1 );
下面,我们可以把有重复数字的情况转化为没有重复数字的。
【在 p*****2 的大作中提到】 : : 对。不然就是DP了。
|
p*****2 发帖数: 21240 | 24
好像很复杂的样子,能不能用例子走一遍呢?
【在 l*********8 的大作中提到】 : (刚写错了一点儿,改了一下) : First, let's look at the situation when no repeated numbers in the : array. : Problem: : Given array A that has n unique positive integers, find the count of : the combinations that have sum m; 0: int S[n][m+1]; : S[i][j]: 取出的数字最大下标为i, 而且这些数字求和为j的combination count : S[i][0] = 0; (后来发现这是没有用的, 如果想省空间,可以用S[*][j]存储求和必须为 : j+1的count)
|
g**********y 发帖数: 14569 | 25 定义dp[] = new int[MAX_SUM]; dp[i]表示用数组a[]可以生成sum = i的办法次数。
dp[i] = sum(dp[i-a[j]]) (j=0..a.length)
【在 p*****2 的大作中提到】 : : 好像很复杂的样子,能不能用例子走一遍呢?
|
p*****2 发帖数: 21240 | 26
你能不能走一下题目里的例子呢?
【在 g**********y 的大作中提到】 : 定义dp[] = new int[MAX_SUM]; dp[i]表示用数组a[]可以生成sum = i的办法次数。 : dp[i] = sum(dp[i-a[j]]) (j=0..a.length)
|
l*********8 发帖数: 4642 | 27 Input:
A[] = {2 3 1}
n = 3 // array size
m = 3 // target of sum
----
定义 matrix S[3][4]
(S[i][j]: 取出的数字最大下标为i, 而且这些数字求和为j的combination count
)
for (int i=0; i
for (int j=1; j<=m; j++)
S[i][j] = 0;
S[0][A[0]] = 1;
0 0 1 0
0 0 0 0
0 0 0 0
for (int i = 1; i < n; i++) {
for (int j=1; j<=m; j++) {
if (A[i] > j) {
S[i][j] = 0;
} else if (A[i] == j) {
S[i][j] = 1;
} else {
for (int k=0; k
S[i][j] += S[k][j-A[i]];
}
}
}
i==1
0 0 1 0
0 0 0 1
0 0 0 0
i==2
a[i] = 1;
j = 1时,S[2][1] = 1; // sum(a[2]) is 1;
j = 2时,S[2][2] = S[0][1] + S[1][1] = 0
j = 3时,S[2][3] = S[0][2] + S[1][2] = 1 // sum{a[0], a[2]) is 3
0 0 1 0
0 0 0 1
0 0 0 1
int totalCount = 0;
for (int i=0; i
totalCount += S[i][m];
totalCount = S[0][3] + S[1][3] + S[2][3] = 2;
【在 p*****2 的大作中提到】 : : 你能不能走一下题目里的例子呢?
|
l*********8 发帖数: 4642 | 28 这个解法是assume数组中的元素可以使用无限次吧?
【在 g**********y 的大作中提到】 : 定义dp[] = new int[MAX_SUM]; dp[i]表示用数组a[]可以生成sum = i的办法次数。 : dp[i] = sum(dp[i-a[j]]) (j=0..a.length)
|
J***2 发帖数: 135 | |
l*********8 发帖数: 4642 | 30 Dynamic programming
【在 J***2 的大作中提到】 : DP是什么的缩写?
|
|
|
p*****2 发帖数: 21240 | 31
count
这个好像没问题。这个是经典算法吗?
【在 l*********8 的大作中提到】 : Input: : A[] = {2 3 1} : n = 3 // array size : m = 3 // target of sum : ---- : 定义 matrix S[3][4] : (S[i][j]: 取出的数字最大下标为i, 而且这些数字求和为j的combination count : ) : for (int i=0; i: for (int j=1; j<=m; j++)
|
l*********8 发帖数: 4642 | 32 我从经典的0-1背包问题修改过来的
【在 p*****2 的大作中提到】 : : count : 这个好像没问题。这个是经典算法吗?
|
p*****2 发帖数: 21240 | 33
我一开始是火鸡的思路,后来发现不对。有时间得好好研究一下背包问题。
【在 l*********8 的大作中提到】 : 我从经典的0-1背包问题修改过来的
|
l*********8 发帖数: 4642 | 34 我前面的核心程序段是三重循环,时间复杂度O(m * n^2)
空间复杂度是O(n*(m+1))
原来的递推公式是:
if A[i]>j
S[i][j] = 0;
else if A[i] == j
S[i][j] = 1;
else
S[i][j] = sum (S[k][j-A[j]] | when k = 0...i-1 );
可以优化为
if A[i]>j
S[i][j] = 0;
else if A[i] == j
S[i][j] = 1;
else
S[i][j] = SS[i-1][j-A[j]] // SS[x][y] 代表 sum (S[k][y]} | when
k = 0...k );
而SS递推公式如下:
SS[i][j] = SS[i-1][j] + S[i][j];
这样,时间复杂度就成为 O(m*n)了 |
l*********8 发帖数: 4642 | 35 火鸡的解法可以看做“无限背包”解法的变种
【在 p*****2 的大作中提到】 : : 我一开始是火鸡的思路,后来发现不对。有时间得好好研究一下背包问题。
|
g**********y 发帖数: 14569 | 36 a = [1, 2, 3, 4, 5], sum = 15
dp[] = new int[16]
initialize dp[0] = 1
依次考虑a[i], 计算结果:
1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0
1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0
1 1 1 2 1 1 1 0 0 0 0 0 0 0 0 0
1 1 1 2 2 2 2 2 1 1 1 0 0 0 0 0
1 1 1 2 2 3 3 3 3 3 3 2 2 1 1 1
最后,count = 1
Java code ->
private void count(int[] a, int sum) {
int[] dp = new int[sum+1];
dp[0] = 1;
for (int i=0; i
for (int j=sum-a[i]; j>=0; j--) {
dp[j+a[i]] += dp[j];
}
}
System.out.println(dp[sum]);
}
对a = [5, 5, 3, 10, 3], 计算过程:
1 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0
1 0 0 0 0 2 0 0 0 0 1 0 0 0 0 0
1 0 0 0 0 2 0 0 0 0 2 0 0 0 0 2
1 0 1 0 0 2 0 2 0 0 2 0 2 0 0 2
1 0 1 1 0 3 0 2 2 0 4 0 2 2 0 4
count = 4
【在 p*****2 的大作中提到】 : : 我一开始是火鸡的思路,后来发现不对。有时间得好好研究一下背包问题。
|
g**********y 发帖数: 14569 | 37 没有,只允许使用1次
【在 l*********8 的大作中提到】 : 这个解法是assume数组中的元素可以使用无限次吧?
|
g**********y 发帖数: 14569 | 38 一维数组就可以,只是需要倒着计算
count
【在 l*********8 的大作中提到】 : Input: : A[] = {2 3 1} : n = 3 // array size : m = 3 // target of sum : ---- : 定义 matrix S[3][4] : (S[i][j]: 取出的数字最大下标为i, 而且这些数字求和为j的combination count : ) : for (int i=0; i: for (int j=1; j<=m; j++)
|
l*********8 发帖数: 4642 | 39 Look at the new formulas again:
if A[i]>j
S[i][j] = 0;
else if A[i] == j
S[i][j] = 1;
else
S[i][j] = SS[i-1][j-A[j]] // SS[x][y] 代表 sum (S[k][y]} | when
k = 0...k );
SS[i][j] = SS[i-1][j] + S[i][j];
Every time we only use SS[i-1][j]. So SS[i-2][*], SS[i-3][*] ... are not
useful and don't need to be saved.
So we use an array, int SS[m] to do same job. Just denote SS[j] as "up to
now, the count of the combinations that have numbers sum to j".
Similarly, we can reduce S from a matrix to an array.
The updated program is as following:
int GetCombinationNumber(vector A, int targetSum)
{
int n = A.size();
int m = targetSum;
vector S;
vector SS;
S.resize(m+1, 0); // init S to 0
S[A[0]] = 1;
SS = S;
for (int i = 1; i < n; i++) {
for (int j=1; j<=m; j++) {
if (A[i] > j) {
S[j] = 0;
} else if (A[i] == j) {
S[j] = 1;
} else {
S[j] = SS[j-A[i]];
}
}
for (int j=1; j<=m; j++) {
SS[j] += S[j];
}
}
return SS[m];
}
【在 l*********8 的大作中提到】 : 我前面的核心程序段是三重循环,时间复杂度O(m * n^2) : 空间复杂度是O(n*(m+1)) : 原来的递推公式是: : if A[i]>j : S[i][j] = 0; : else if A[i] == j : S[i][j] = 1; : else : S[i][j] = sum (S[k][j-A[j]] | when k = 0...i-1 ); : 可以优化为
|
p*****2 发帖数: 21240 | 40
这个太牛了。得好好学习一下。多谢火鸡了。
【在 g**********y 的大作中提到】 : a = [1, 2, 3, 4, 5], sum = 15 : dp[] = new int[16] : initialize dp[0] = 1 : 依次考虑a[i], 计算结果: : 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 : 1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 : 1 1 1 2 1 1 1 0 0 0 0 0 0 0 0 0 : 1 1 1 2 2 2 2 2 1 1 1 0 0 0 0 0 : 1 1 1 2 2 3 3 3 3 3 3 2 2 1 1 1 : 最后,count = 1
|
|
|
l*********8 发帖数: 4642 | 41 Look at the formulas once more:
if A[i]>j
S[i][j] = 0;
else if A[i] == j
S[i][j] = 1;
else
S[i][j] = SS[i-1][j-A[j]] // SS[x][y] 代表 sum (S[k][y]} | when
k = 0...k );
SS[i][j] = SS[i-1][j] + S[i][j];
maybe we only need SS but not S.
if A[i] > j
SS[i][j] == SS[i-1][j]
else if A[i] == j
SS[i][j] = SS[i-1][j] + 1;
else
SS[i][j] += SS[i-1][j-A[j]];
If we use j-- instead of j++ for the loop
then we have
if A[i] > j
SS[j] == SS[j]
else if A[i] == j
SS[j] = SS[j] + 1;
else
SS[j] += SS[j-A[j]];
if we set SS[0] = 1;
then we have
if A[i] > j
SS[j] == SS[j]
else
SS[j] += SS[j-A[j]];
Updated program:
int GetCombinationNumber(vector A, int m)
{
vector SS;
SS.resize(m+1, 0); // init SS to 0
SS[0] = 1;
for (int i = 0; i < A.size(); i++) {
for (int j=m; j>=A[i]; j--) {
S[j] += SS[j-A[i]];
}
}
return SS[m];
}
It turned out to be gloomyturkey's program .....
Thanks a lot, gloomyturkey!
|
h*****g 发帖数: 312 | 42 火鸡 太牛了 我当时没想到 可以倒着走,用的是 n*sum 空间。但要是想print 满足条
件的答案,还得需要 n*sum吧?
【在 g**********y 的大作中提到】 : a = [1, 2, 3, 4, 5], sum = 15 : dp[] = new int[16] : initialize dp[0] = 1 : 依次考虑a[i], 计算结果: : 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 : 1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 : 1 1 1 2 1 1 1 0 0 0 0 0 0 0 0 0 : 1 1 1 2 2 2 2 2 1 1 1 0 0 0 0 0 : 1 1 1 2 2 3 3 3 3 3 3 2 2 1 1 1 : 最后,count = 1
|
h*****g 发帖数: 312 | 43 火鸡 太牛了 我当时没想到 可以倒着走,用的是 n*sum 空间。但要是想print 满足条
件的答案,还得需要 n*sum吧?
【在 g**********y 的大作中提到】 : a = [1, 2, 3, 4, 5], sum = 15 : dp[] = new int[16] : initialize dp[0] = 1 : 依次考虑a[i], 计算结果: : 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 : 1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 : 1 1 1 2 1 1 1 0 0 0 0 0 0 0 0 0 : 1 1 1 2 2 2 2 2 1 1 1 0 0 0 0 0 : 1 1 1 2 2 3 3 3 3 3 3 2 2 1 1 1 : 最后,count = 1
|
g**********y 发帖数: 14569 | 44 要print, 就有可能是指数级的了,因为答案数可以是指数级。
【在 h*****g 的大作中提到】 : 火鸡 太牛了 我当时没想到 可以倒着走,用的是 n*sum 空间。但要是想print 满足条 : 件的答案,还得需要 n*sum吧?
|
l*********8 发帖数: 4642 | 45 time可能是指数级的, 但space应该就是O(n*m)吧?
【在 g**********y 的大作中提到】 : 要print, 就有可能是指数级的了,因为答案数可以是指数级。
|
g**********y 发帖数: 14569 | 46 对。
【在 l*********8 的大作中提到】 : time可能是指数级的, 但space应该就是O(n*m)吧?
|