p*****e 发帖数: 53 | 1 给定一个array和一个固定值sum,
找出array中加和等于sum的最少元素个数
array中肯定有{1}这个元素,除了{1}这个元素只能用一次意外,其他元素可以重复使用
例如 arr={90,30,18,15,10,5,3,2,1} sum=32
则返回2, 即最小的组合是两个数{30,2}
哪位给说说这个怎么做最高效?
非常感谢! |
s*****y 发帖数: 897 | 2 you want better than DP?
使用
【在 p*****e 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 给定一个array和一个固定值sum, : 找出array中加和等于sum的最少元素个数 : array中肯定有{1}这个元素,除了{1}这个元素只能用一次意外,其他元素可以重复使用 : 例如 arr={90,30,18,15,10,5,3,2,1} sum=32 : 则返回2, 即最小的组合是两个数{30,2} : 哪位给说说这个怎么做最高效? : 非常感谢!
|
p*****e 发帖数: 53 | 3 DP怎么解,大牛能给个code吗?
我一听DP头就大:(
【在 s*****y 的大作中提到】![](/moin_static193/solenoid/img/up.png) : you want better than DP? : : 使用
|
d*******d 发帖数: 2050 | |
p*****e 发帖数: 53 | 5 太感谢了,新手问题总是比较水
刚刚你提醒了,我放狗搜到了
这就去学习。
再次感谢!
【在 d*******d 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 这不是dp找钱问题么
|
i**********e 发帖数: 1145 | |
p*****e 发帖数: 53 | 7 谢谢ihasleetcode!特别喜欢你的编程网站
去你的网站搜了,没有类似的题
所以就来这里求助了
马上去看你给的link:)
【在 i**********e 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 对,是数硬币的 dp 。 : 很好的教程介绍: : http://www.topcoder.com/tc?d1=tutorials&d2=dynProg&module=Stati
|
s*****y 发帖数: 897 | 8 刚才想贴code给你,但是你的题目1只能够用一次,我以前写的1可以用无数次的
要改一下,虽然答案出来的也是一样的。
【在 p*****e 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 谢谢ihasleetcode!特别喜欢你的编程网站 : 去你的网站搜了,没有类似的题 : 所以就来这里求助了 : 马上去看你给的link:)
|
p*****e 发帖数: 53 | 9 非常感谢!
我对这类题都有点蒙,特别是DP
能把你的code贴一下吗?想学习学习
【在 s*****y 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 刚才想贴code给你,但是你的题目1只能够用一次,我以前写的1可以用无数次的 : 要改一下,虽然答案出来的也是一样的。
|
w*****3 发帖数: 101 | 10 这个可以预处理一下么,
在去掉1的数组里找sum - 1 和sum,
最后比较dp[sum - 1] + 1 和 dp[sum]的大小
【在 s*****y 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 刚才想贴code给你,但是你的题目1只能够用一次,我以前写的1可以用无数次的 : 要改一下,虽然答案出来的也是一样的。
|
|
|
i**********e 发帖数: 1145 | 11 代码比较乱,因为在实现的时候没有 +INF 这个定义。
逻辑是根据 topcoder tutorial 的思路。最后为了确保 ‘1’只用一次,那就比较 dp
的 table, dp[target] 和 1+dp[target-1] 哪一个比较小就可以了。
// return INT_MAX when there's no valid sum
int minNumThatSumToTarget(int A[], int n, int target) {
assert(target > 0);
int *dp = new int[target+1];
for (int i = 1; i <= target; i++)
dp[i] = INT_MAX;
dp[0] = 0;
for (int i = 1; i <= target; i++) {
for (int j = 0; j < n; j++) {
if (A[j] == 1) continue;
if (i - A[j] >= 0 && dp[i-A[j]] != INT_MAX)
dp[i] = min(dp[i], 1+dp[i-A[j]]);
}
}
int ret = dp[target];
if (dp[target-1] != INT_MAX)
ret = min(ret, 1+dp[target-1]);
delete[] dp;
return ret;
}
【在 p*****e 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 非常感谢! : 我对这类题都有点蒙,特别是DP : 能把你的code贴一下吗?想学习学习
|
s*****y 发帖数: 897 | 12 #include
#include
#include
#include
using namespace std;
vector FindSet(int target, const vector &input)
{
vector rtn;
int dp[10][100]; //dp table to save the result
bool used[10][100];
for (int i = 0; i <= target; i++) {
dp[0][i] = 0;
if (i <= 1) {
dp[1][i] = i;
used[1][i] = true;
} else {
dp[1][i] = INT_MAX;
used[1][i] = false;
}
}
for (int i = 2; i <= input.size(); i++) {
dp[i][0] = 0;
dp[i][1] = 1;
for (int j = 2; j <= target; j++) {
if ((input[i-1] <= j) && (dp[i][j-input[i-1]] + 1 < dp[i-1][j]))
{
dp[i][j] = dp[i][j-input[i-1]] + 1;
used[i][j] = true;
} else {
used[i][j] = false;
dp[i][j] = dp[i-1][j];
}
}
}
cout << " Best solution is " << dp[input.size()][target] << endl;
//reconstruct the solution
int i = input.size();
int j = target;
while(j > 0) {
if (used[i][j]) {
cout << " Put:" << input[i-1] << endl;
rtn.push_back(input[i-1]);
j -= input[i-1];
} else {
i = i-1;
}
}
return rtn;
}
int main(int argc, char* argv[])
{
int target = 32;
int data[] = {1,2,3,5,10,15,18,30,90};
vector contain(data, data + sizeof(data)/sizeof(int));
vector result = FindSet(target, contain);
return 1;
} |
g**********y 发帖数: 14569 | 13 Java version:
public int solve(int[] a, int sum) {
HashSet set = new HashSet();
for (int i : a) set.add(i);
set.remove(1);
int[] m = new int[sum+1];
m[1] = 1;
for (int i=2; i<=sum; i++) {
m[i] = sum+1;
for (int j : set) {
if (j<=i) m[i] = Math.min(m[i], 1+m[i-j]);
}
}
return m[sum];
} |
s*****y 发帖数: 897 | 14 似乎除了我得code,大家都是ouput最后的可以用多少个数得到值,但是没有output30
和2。 |
s*****y 发帖数: 897 | 15 似乎除了我得code,大家都是ouput最后的可以用多少个数得到值,但是没有output30
和2。 |
p*****e 发帖数: 53 | 16 非常感谢你的code,拜读了
题目没有要求输出组合,所以只要输出多少个数就可以了
output30
【在 s*****y 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 似乎除了我得code,大家都是ouput最后的可以用多少个数得到值,但是没有output30 : 和2。
|
t**r 发帖数: 3428 | |
s*****y 发帖数: 897 | 18 最好准备输出
看这个google 题
http://www.careercup.com/question?id=9615934
如果你的1不是只用1次,跟这题是一样的。
you are given following:
1. An empty tank
2. Unlimited source of water.
3. Some container of certain measurments and a container of 1 litre is
always given.
Your job is to fill the tank from source of water using the containers in
minimum number of steps.
You cant fill the container with a small amount of water than its size (
filling partially is not allowed).
Find the number of steps and print the solution.
e.g.
Tank Size: 80 litre
Containers: 1,3,5,6,25 litre
Solution:
4
5,25,25,25
Tank Size: 71 litre
Containers: 1,3,5,6,25 litre
Solution:
6
3,6,6,6,25,25
12
【在 p*****e 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 非常感谢你的code,拜读了 : 题目没有要求输出组合,所以只要输出多少个数就可以了 : : output30
|
g**********y 发帖数: 14569 | 19 带输出的,不用分配那么多空间,只要记住parent index就行。
public int solve2(int[] a, int sum) {
ArrayList numbers = new ArrayList();
for (int i : a) if (i!=1) numbers.add(i);
int[][] m = new int[sum+1][2];
m[0] = new int[]{0, -1};
m[1] = new int[]{1, 0};
for (int i=2; i<=sum; i++) {
m[i] = new int[]{sum+1, -1};
for (int j : numbers) {
if (j<=i && m[i][0] > 1+m[i-j][0]) {
m[i][0] = 1+m[i-j][0];
m[i][1] = i - j;
}
}
}
print(m, sum);
return m[sum][0];
}
private void print(int[][] m, int sum) {
for (int i=sum; i>0; ) {
System.out.print(i - m[i][1] + " ");
i = m[i][1];
}
System.out.println();
}
output30
【在 s*****y 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 似乎除了我得code,大家都是ouput最后的可以用多少个数得到值,但是没有output30 : 和2。
|
e***s 发帖数: 799 | 20 仔细研究了大哥的CODE,空间复杂度会不会太高?而且如果TARGET > 100 就不行了。
是不是边界问题?
【在 s*****y 的大作中提到】![](/moin_static193/solenoid/img/up.png) : #include : #include : #include : #include : using namespace std; : vector FindSet(int target, const vector &input) : { : vector rtn; : int dp[10][100]; //dp table to save the result : bool used[10][100];
|
|
|
s*****y 发帖数: 897 | 21 是挺高的,>100的话就把array设置大点就好了。
看火鸡的代码,他那个是最好的,
因为我在开始学习dp的时候,想存储中间所有的结果,这样有助于我debug的时候看每
一个中间的状态,然后再回头去压缩那个空间。
【在 e***s 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 仔细研究了大哥的CODE,空间复杂度会不会太高?而且如果TARGET > 100 就不行了。 : 是不是边界问题?
|
p*****e 发帖数: 53 | 22 这个DP算法要记录所有的target-1的结果
如果target 很大,例如100000 或者更高是不是就不能用了
如果是那样用什么方法呢?
谢谢
dp
【在 i**********e 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 代码比较乱,因为在实现的时候没有 +INF 这个定义。 : 逻辑是根据 topcoder tutorial 的思路。最后为了确保 ‘1’只用一次,那就比较 dp : 的 table, dp[target] 和 1+dp[target-1] 哪一个比较小就可以了。 : // return INT_MAX when there's no valid sum : int minNumThatSumToTarget(int A[], int n, int target) { : assert(target > 0); : int *dp = new int[target+1]; : for (int i = 1; i <= target; i++) : dp[i] = INT_MAX; : dp[0] = 0;
|
p*****e 发帖数: 53 | 23 是不是DP算法只能用于比较小的target呀
如果target很大,那即使不记录中间状态,也需要记录所有target-1状态
如果是这种情况,除了DP还有别更有效的算法吗?
【在 s*****y 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 是挺高的,>100的话就把array设置大点就好了。 : 看火鸡的代码,他那个是最好的, : 因为我在开始学习dp的时候,想存储中间所有的结果,这样有助于我debug的时候看每 : 一个中间的状态,然后再回头去压缩那个空间。
|
a*********0 发帖数: 2727 | 24 允许有负数的情况么?如果有负数怎么用dp?
使用
【在 p*****e 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 给定一个array和一个固定值sum, : 找出array中加和等于sum的最少元素个数 : array中肯定有{1}这个元素,除了{1}这个元素只能用一次意外,其他元素可以重复使用 : 例如 arr={90,30,18,15,10,5,3,2,1} sum=32 : 则返回2, 即最小的组合是两个数{30,2} : 哪位给说说这个怎么做最高效? : 非常感谢!
|
p*****e 发帖数: 53 | 25 没有负数,但是数组内的元素如果很大的话,比如10000
加和为100000的情况是不是也不能用dp了?
【在 a*********0 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 允许有负数的情况么?如果有负数怎么用dp? : : 使用
|
w*****3 发帖数: 101 | |
a***y 发帖数: 2803 | 27 怎么用到了2维array?
【在 s*****y 的大作中提到】![](/moin_static193/solenoid/img/up.png) : #include : #include : #include : #include : using namespace std; : vector FindSet(int target, const vector &input) : { : vector rtn; : int dp[10][100]; //dp table to save the result : bool used[10][100];
|
e***s 发帖数: 799 | 28 仔细想了想这个问题,因为给出的array有, 1, 2. 所以后面的条件说{1}只能用一次是
多余的,如果{1}用了两次,证明你的解不是optimal, 如果是optimal的解,{1}不会用多
于一次. |
e***s 发帖数: 799 | 29 #include
#include
#include
#include
#include
using namespace std;
vector FindSet(unsigned int sum, vector &coinset)
{
vector rtn;
int *Min = new int[sum + 1];
vector *Combination = new vector[sum + 1];
Min[0] = 0;
unsigned int i;
unsigned int j;
for(i = 1; i <= sum; i++)
{
Min[i] = INT_MAX;
}
for(i = 1; i <= sum; i++)
{
for(j = 0; j < coinset.size(); j++)
{
if(i>=coinset[j] && Min[i - coinset[j]] < Min[i])
{
Min[i] = Min[i - coinset[j]] + 1;
Combination[i] = Combination[i - coinset[j]];
Combination[i].push_back(coinset[j]);
}
}
}
cout << "Min: " << Min[sum] << endl;
cout << "Combination is: ";
for(i = 0; i < Combination[sum].size(); i++)
{
cout << " " << Combination[sum][i];
}
cout << endl;
delete Min;
Min = 0;
return rtn;
}
int main()
{
int sum = 11;
int coin[3] = {1, 3, 5};
vector coinset(coin, coin + sizeof(coin)/sizeof(unsigned
int));
vector result = FindSet(sum, coinset);
return 1;
} |
c******r 发帖数: 225 | 30 我的理解是,这个特例有2,如果没有2,就得track 1 被用了几次
我觉得这个题用DP可以生成两个数组
A1记录min(sum) on set of all candidates
A2记录min(sum-1) on set of all candidates minus {1}
最后A3[i]=min(A1[i],A2[i-1]+1) for i>1
A3[0]=0 when i=1
这个可以推广到任意数都只能用一次的情况
【在 e***s 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 仔细想了想这个问题,因为给出的array有, 1, 2. 所以后面的条件说{1}只能用一次是 : 多余的,如果{1}用了两次,证明你的解不是optimal, 如果是optimal的解,{1}不会用多 : 于一次.
|