由买买提看人间百态

boards

本页内容为未名空间相应帖子的节选和存档,一周内的贴子最多显示50字,超过一周显示500字 访问原贴
JobHunting版 - 这题也可以DP 解吧?
相关主题
CS: print all combination from an arraygenerate unique integer ID from columns in SQL table
a problem from leetcode: high efficiency algorithm for combinations problem问一道老题
这题怎么做?这题怎么做?
请教一个常见的面试题的答案combinations 有没有 iterative的方法阿 ?
a[i] + b[j] = c[k] 的题有靠谱的答案不?问个递归的问题
请教leetcode Combination Sum II的code,谢谢。请教这题怎么做啊
Combination Sum II哪里做错了combination sum这题的复杂度?
关于结果除掉重复的问题请教这题如何破?
相关话题的讨论汇总
话题: ss话题: int话题: sum话题: else话题: dp
进入JobHunting版参与讨论
1 (共1页)
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
7
我怎么看着不像DP?这题用bit那个方法可解。
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 的大作中提到】
: 经典背包要求物品的总体积小于等于某个值。 这个问题要求“物品总体积”等于某个值
相关主题
请教leetcode Combination Sum II的code,谢谢。generate unique integer ID from columns in SQL table
Combination Sum II哪里做错了问一道老题
关于结果除掉重复的问题请教这题怎么做?
进入JobHunting版参与讨论
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)还是有
: 点区别的哦。~~~~

相关主题
combinations 有没有 iterative的方法阿 ?combination sum这题的复杂度?
问个递归的问题这题如何破?
请教这题怎么做啊Google电话面试题目
进入JobHunting版参与讨论
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
29
DP是什么的缩写?
l*********8
发帖数: 4642
30
Dynamic programming

【在 J***2 的大作中提到】
: DP是什么的缩写?
相关主题
请教几个问题a problem from leetcode: high efficiency algorithm for combinations problem
做题这题怎么做?
CS: print all combination from an array请教一个常见的面试题的答案
进入JobHunting版参与讨论
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

相关主题
请教一个常见的面试题的答案Combination Sum II哪里做错了
a[i] + b[j] = c[k] 的题有靠谱的答案不?关于结果除掉重复的问题请教
请教leetcode Combination Sum II的code,谢谢。generate unique integer ID from columns in SQL table
进入JobHunting版参与讨论
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)吧?
1 (共1页)
进入JobHunting版参与讨论
相关主题
这题如何破?a[i] + b[j] = c[k] 的题有靠谱的答案不?
Google电话面试题目请教leetcode Combination Sum II的code,谢谢。
请教几个问题Combination Sum II哪里做错了
做题关于结果除掉重复的问题请教
CS: print all combination from an arraygenerate unique integer ID from columns in SQL table
a problem from leetcode: high efficiency algorithm for combinations problem问一道老题
这题怎么做?这题怎么做?
请教一个常见的面试题的答案combinations 有没有 iterative的方法阿 ?
相关话题的讨论汇总
话题: ss话题: int话题: sum话题: else话题: dp