y*****f
发帖数: 1073 | 1 一个朋友问俺的，工作上的问题，一时想不出啥好算法，求高手指点迷津。
给定一个总数，还有几十个数字。
从这几十个数字里，找出这个总数是由哪些数字累加出来的？
有啥效率比较高的算法么？ |
s******y
发帖数: 936 | 2 leetcode 的combination sum吧 |
g**********y
发帖数: 14569 | 3 总数固定，就可以用DP解, dp[]记录可以到达的前一点(parent). 大致是：
int[] dp = new int[N+1];
init(dp); // set all to -1
dp[0] = 0;
for(int i : a) {
for (int j=N; j>=i; j--) {
if (dp[j-i] >= 0) dp[j] = j-i;
}
}
if (dp[N] > 0) {
backtrace_solution();
} else {
// no solution
}
【在 y*****f 的大作中提到】
: 一个朋友问俺的，工作上的问题，一时想不出啥好算法，求高手指点迷津。
: 给定一个总数，还有几十个数字。
: 从这几十个数字里，找出这个总数是由哪些数字累加出来的？
: 有啥效率比较高的算法么？
|
y*****f
发帖数: 1073 | 4 嗯，找到了，确实是这个，多谢。
【在 s******y 的大作中提到】
: leetcode 的combination sum吧
|
y*****f
发帖数: 1073 | 5 还没仔细读代码，先谢谢了。
【在 g**********y 的大作中提到】
: 总数固定，就可以用DP解, dp[]记录可以到达的前一点(parent). 大致是：
: int[] dp = new int[N+1];
: init(dp); // set all to -1
: dp[0] = 0;
: for(int i : a) {
: for (int j=N; j>=i; j--) {
: if (dp[j-i] >= 0) dp[j] = j-i;
: }
: }
: if (dp[N] > 0) {
|
g**********y
发帖数: 14569 | 6 代码修改了，应该逆向算。
【在 y*****f 的大作中提到】
: 还没仔细读代码，先谢谢了。
|
g*********e
发帖数: 14401 | 7 subset sum np complete
【在 y*****f 的大作中提到】
: 一个朋友问俺的，工作上的问题，一时想不出啥好算法，求高手指点迷津。
: 给定一个总数，还有几十个数字。
: 从这几十个数字里，找出这个总数是由哪些数字累加出来的？
: 有啥效率比较高的算法么？
|
f****8
发帖数: 33 | 8 如果是COMBINATION SUM（允许数字重复）的话，那就是COIN问题的翻版啦，非常典型
的DP问题。
但如果换成其他问题，例如数字里面有正数有负数，N SUM问题的话，就是NP了 |
