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 的大作中提到】
: 给定一个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 的大作中提到】
: you want better than DP?
:
: 使用
|
d*******d
发帖数: 2050 | |
p*****e
发帖数: 53 | 5 太感谢了，新手问题总是比较水
刚刚你提醒了，我放狗搜到了
这就去学习。
再次感谢！
【在 d*******d 的大作中提到】
: 这不是dp找钱问题么
|
i**********e
发帖数: 1145 | |
p*****e
发帖数: 53 | 7 谢谢ihasleetcode！特别喜欢你的编程网站
去你的网站搜了，没有类似的题
所以就来这里求助了
马上去看你给的link:)
【在 i**********e 的大作中提到】
: 对，是数硬币的 dp 。
: 很好的教程介绍：
: http://www.topcoder.com/tc?d1=tutorials&d2=dynProg&module=Stati
|
s*****y
发帖数: 897 | 8 刚才想贴code给你，但是你的题目1只能够用一次，我以前写的1可以用无数次的
要改一下，虽然答案出来的也是一样的。
【在 p*****e 的大作中提到】
: 谢谢ihasleetcode！特别喜欢你的编程网站
: 去你的网站搜了，没有类似的题
: 所以就来这里求助了
: 马上去看你给的link:)
|
p*****e
发帖数: 53 | 9 非常感谢！
我对这类题都有点蒙，特别是DP
能把你的code贴一下吗？想学习学习
【在 s*****y 的大作中提到】
: 刚才想贴code给你，但是你的题目1只能够用一次，我以前写的1可以用无数次的
: 要改一下，虽然答案出来的也是一样的。
|
w*****3
发帖数: 101 | 10 这个可以预处理一下么，
在去掉1的数组里找sum - 1 和sum，
最后比较dp[sum - 1] + 1 和 dp[sum]的大小
【在 s*****y 的大作中提到】
: 刚才想贴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 的大作中提到】
: 非常感谢！
: 我对这类题都有点蒙，特别是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 的大作中提到】
: 似乎除了我得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 的大作中提到】
: 非常感谢你的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 的大作中提到】
: 似乎除了我得code，大家都是ouput最后的可以用多少个数得到值，但是没有output30
: 和2。
|
e***s
发帖数: 799 | 20 仔细研究了大哥的CODE，空间复杂度会不会太高？而且如果TARGET > 100 就不行了。
是不是边界问题？
【在 s*****y 的大作中提到】
: #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 的大作中提到】
: 仔细研究了大哥的CODE，空间复杂度会不会太高？而且如果TARGET > 100 就不行了。
: 是不是边界问题？
|
p*****e
发帖数: 53 | 22 这个DP算法要记录所有的target-1的结果
如果target 很大，例如100000 或者更高是不是就不能用了
如果是那样用什么方法呢？
谢谢
dp
【在 i**********e 的大作中提到】
: 代码比较乱，因为在实现的时候没有 +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 的大作中提到】
: 是挺高的,>100的话就把array设置大点就好了。
: 看火鸡的代码,他那个是最好的,
: 因为我在开始学习dp的时候，想存储中间所有的结果，这样有助于我debug的时候看每
: 一个中间的状态，然后再回头去压缩那个空间。
|
a*********0
发帖数: 2727 | 24 允许有负数的情况么？如果有负数怎么用dp?
使用
【在 p*****e 的大作中提到】
: 给定一个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 的大作中提到】
: 允许有负数的情况么？如果有负数怎么用dp?
:
: 使用
|
w*****3
发帖数: 101 | |
a***y
发帖数: 2803 | 27 怎么用到了2维array?
【在 s*****y 的大作中提到】
: #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 我的理解是，这个特例有２，如果没有２，就得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 的大作中提到】
: 仔细想了想这个问题,因为给出的array有, 1, 2. 所以后面的条件说{1}只能用一次是
: 多余的,如果{1}用了两次,证明你的解不是optimal, 如果是optimal的解,{1}不会用多
: 于一次.
|
