j**l 发帖数: 2911 | 1 我想这题和背包一样是NP的,不知道是否是要用动态规划来解?
有N种邮票,面值分别为v_1, v_2, ..., v_N, 张数分别为c_1, c_2, ..., c_N。现在
要邮寄的包裹需要的邮资是V, 如何选取邮票,使得总面值>=V, 且尽可能的小。
N, v_1, v_2, ..., v_N, c_1, c_2, ..., c_N都是给定的正整数。 | s*****y 发帖数: 897 | 2 what do you mean 尽可能的小?
【在 j**l 的大作中提到】 : 我想这题和背包一样是NP的,不知道是否是要用动态规划来解? : 有N种邮票,面值分别为v_1, v_2, ..., v_N, 张数分别为c_1, c_2, ..., c_N。现在 : 要邮寄的包裹需要的邮资是V, 如何选取邮票,使得总面值>=V, 且尽可能的小。 : N, v_1, v_2, ..., v_N, c_1, c_2, ..., c_N都是给定的正整数。
| j**l 发帖数: 2911 | 3 必须perfect pay,或者over pay, 不能under pay,
但又想over pay的尽可能少,如果不能perfect pay的话
举个例子就知道了。
比如面值为2分,5分,8分,10分,12分的邮票各一张,邮资是16分,
就选2分,5分,10分,或者选5分,12分,都是over pay了1分。
【在 s*****y 的大作中提到】 : what do you mean 尽可能的小?
| g*********s 发帖数: 1782 | 4 in this case i think 5 + 12 is better.
【在 j**l 的大作中提到】 : 必须perfect pay,或者over pay, 不能under pay, : 但又想over pay的尽可能少,如果不能perfect pay的话 : 举个例子就知道了。 : 比如面值为2分,5分,8分,10分,12分的邮票各一张,邮资是16分, : 就选2分,5分,10分,或者选5分,12分,都是over pay了1分。
| r****k 发帖数: 173 | | o*******p 发帖数: 722 | 6 No, it is impossible to solve this problem by dynamic programming because
this problem doesn't exhibit optimal substructure.
For example, postage of 8 cents is a subprogram of postage of 16 cents. But
the optimal solution for 8 cents is just one 8 cents stamp, which is not
part of the optimal solution for postage of 16 cents.
I guess this problem is NPC.
【在 j**l 的大作中提到】 : 必须perfect pay,或者over pay, 不能under pay, : 但又想over pay的尽可能少,如果不能perfect pay的话 : 举个例子就知道了。 : 比如面值为2分,5分,8分,10分,12分的邮票各一张,邮资是16分, : 就选2分,5分,10分,或者选5分,12分,都是over pay了1分。
| s*****y 发帖数: 897 | 7 Agree. Seems not fulfill the requirement of DP.
But
【在 o*******p 的大作中提到】 : No, it is impossible to solve this problem by dynamic programming because : this problem doesn't exhibit optimal substructure. : For example, postage of 8 cents is a subprogram of postage of 16 cents. But : the optimal solution for 8 cents is just one 8 cents stamp, which is not : part of the optimal solution for postage of 16 cents. : I guess this problem is NPC.
| r****k 发帖数: 173 | 8
because
But
顶牛人
【在 o*******p 的大作中提到】 : No, it is impossible to solve this problem by dynamic programming because : this problem doesn't exhibit optimal substructure. : For example, postage of 8 cents is a subprogram of postage of 16 cents. But : the optimal solution for 8 cents is just one 8 cents stamp, which is not : part of the optimal solution for postage of 16 cents. : I guess this problem is NPC.
| c********0 发帖数: 112 | 9 这个是典型的 LP问题吧。。。
用simplex | s*****y 发帖数: 897 | 10 can you give more detail.
Thanks
【在 c********0 的大作中提到】 : 这个是典型的 LP问题吧。。。 : 用simplex
| | | c********0 发帖数: 112 | 11 比如面值为2分,5分,8分 的邮票各
有a, b, c 张,邮资是16分
假设取2分 5分 8分 的各x,y,z 张
limitation:
0<=x<=a
0<=y<=b
0<=z<=c
2x+5y+8z >= 16
obj: min( 2x+5y+8z )
这是LP问题(他的dual是标准形式)
如果x,y,z都是整数的话是有polynomial解的 通常用simplex运行很快
可以scale到很高的维度
http://en.wikipedia.org/wiki/Linear_programming
但是我感觉通常面试不考LP的。。。 | j**l 发帖数: 2911 | 12 这是一道G的题目...
我觉得:
1) 和多重背包有一定关系,每种物品有若干件,假设物品的价值和重量成正比,这样
总价值最大就是总重量最大。不过要把不超重的情况下尽可能的重,改为超重的情况下
尽可能的轻。既然多重背包可以用动态规划,这题肯定也可以,参考楼教主的背包九讲。
2) 转为LP的问题让我耳目一新。其实我学最优化理论的时候学过单纯型法,但这题没
有想到也可以转为LP问题。不过从1)来看,应该是NPC的,用LP解是伪多项式时间吧。
不少用动态规划解的NPC题,也是伪多项式的,要弄清楚输入规模。
3) 最不济,也要想到暴力穷举法,比如你的例子,对x, y, z作三重循环。如果这个不
说出来,又想不到1)或者2), 面试官那里肯定几乎不得分了。
4) 如果想用贪心法或者硬币找零的动态规划法,这题就走弯路和死胡同了。
比如面值为2分,5分,8分 的邮票各
有a, b, c 张,邮资是16分
假设取2分 5分 8分 的各x,y,z 张
limitation:
0<=x<=a
0<=y<=b
0<=z<=c
2x+5y+8z >= 16
obj: min( 2x+5y+8z )
这是LP问题(他的dual是标准形式)
如果x,y,z都是整数的话是有polynomial解的 通常用simplex运行很快
可以scale到很高的维度
http://en.wikipedia.org/wiki/Linear_programming
但是我感觉通常面试不考LP的。。。
【在 c********0 的大作中提到】 : 比如面值为2分,5分,8分 的邮票各 : 有a, b, c 张,邮资是16分 : 假设取2分 5分 8分 的各x,y,z 张 : limitation: : 0<=x<=a : 0<=y<=b : 0<=z<=c : 2x+5y+8z >= 16 : obj: min( 2x+5y+8z ) : 这是LP问题(他的dual是标准形式)
| a********e 发帖数: 508 | 13 可以定义一个recursive function吧每次先pick up面值v_k的邮票,剩下的邮票
只需要凑足V-v_k。对k循环做比较。但是要call很多次function,时间复杂度不低。。
讲。
【在 j**l 的大作中提到】 : 这是一道G的题目... : 我觉得: : 1) 和多重背包有一定关系,每种物品有若干件,假设物品的价值和重量成正比,这样 : 总价值最大就是总重量最大。不过要把不超重的情况下尽可能的重,改为超重的情况下 : 尽可能的轻。既然多重背包可以用动态规划,这题肯定也可以,参考楼教主的背包九讲。 : 2) 转为LP的问题让我耳目一新。其实我学最优化理论的时候学过单纯型法,但这题没 : 有想到也可以转为LP问题。不过从1)来看,应该是NPC的,用LP解是伪多项式时间吧。 : 不少用动态规划解的NPC题,也是伪多项式的,要弄清楚输入规模。 : 3) 最不济,也要想到暴力穷举法,比如你的例子,对x, y, z作三重循环。如果这个不 : 说出来,又想不到1)或者2), 面试官那里肯定几乎不得分了。
| c********0 发帖数: 112 | 14 LP的问题 如果要求整数解的话不是NPC
每个邮票不是要求必须整数吗。。。
如果可以浮点数的话是NPC
讲。
【在 j**l 的大作中提到】 : 这是一道G的题目... : 我觉得: : 1) 和多重背包有一定关系,每种物品有若干件,假设物品的价值和重量成正比,这样 : 总价值最大就是总重量最大。不过要把不超重的情况下尽可能的重,改为超重的情况下 : 尽可能的轻。既然多重背包可以用动态规划,这题肯定也可以,参考楼教主的背包九讲。 : 2) 转为LP的问题让我耳目一新。其实我学最优化理论的时候学过单纯型法,但这题没 : 有想到也可以转为LP问题。不过从1)来看,应该是NPC的,用LP解是伪多项式时间吧。 : 不少用动态规划解的NPC题,也是伪多项式的,要弄清楚输入规模。 : 3) 最不济,也要想到暴力穷举法,比如你的例子,对x, y, z作三重循环。如果这个不 : 说出来,又想不到1)或者2), 面试官那里肯定几乎不得分了。
| j*******r 发帖数: 20 | 15 这个问题是npc的,可以规约到3-color
这里的线性规划出来的是解是在实数上的,不符合要求
如果限制在整数上,叫整数规划,是npc的。。。 | c********0 发帖数: 112 | 16 我说反了。。。
整数解是NPC
【在 j*******r 的大作中提到】 : 这个问题是npc的,可以规约到3-color : 这里的线性规划出来的是解是在实数上的,不符合要求 : 如果限制在整数上,叫整数规划,是npc的。。。
| j**l 发帖数: 2911 | 17 I did not realize that Brute Force method should be used first, and tried to use Greedy and the idea of Coin problem instead. I eventually got stuck. I finally told him that it should be NPC, but I did not realize that it is a variation of the classic Knapsack problem and let him know. I think he gave bad feedback to the hiring committee.
3) 最不济,也要想到暴力穷举法,比如comon2010的例子,可对x, y, z作三重循环穷举比较。如果这个都不能先说出来,然后又想不到1)或者2), 面试官那里肯定几乎不得分了。 | g***s 发帖数: 3811 | 18 assume v1,v2<...
answer = invalid;
m = V + v_n
while ( (t = 背包(m))>=V){
answer = m;
m = t-1;
}
return answer;
So, we can use 背包 function to solve this problem.
讲。
【在 j**l 的大作中提到】 : 我想这题和背包一样是NP的,不知道是否是要用动态规划来解? : 有N种邮票,面值分别为v_1, v_2, ..., v_N, 张数分别为c_1, c_2, ..., c_N。现在 : 要邮寄的包裹需要的邮资是V, 如何选取邮票,使得总面值>=V, 且尽可能的小。 : N, v_1, v_2, ..., v_N, c_1, c_2, ..., c_N都是给定的正整数。
| o*******p 发帖数: 722 | 19 I would tell the interviewer that I can't solve this problem in polynomial
time, but I do want to know the answer if the interviewer can solve it in
polynomial time, so that I can go to Clay Institute and claim their 1
million dollar prize.
讲。
【在 j**l 的大作中提到】 : 我想这题和背包一样是NP的,不知道是否是要用动态规划来解? : 有N种邮票,面值分别为v_1, v_2, ..., v_N, 张数分别为c_1, c_2, ..., c_N。现在 : 要邮寄的包裹需要的邮资是V, 如何选取邮票,使得总面值>=V, 且尽可能的小。 : N, v_1, v_2, ..., v_N, c_1, c_2, ..., c_N都是给定的正整数。
| g***s 发帖数: 3811 | 20 interviewer can solve it as i think.
polynomial
in
【在 o*******p 的大作中提到】 : I would tell the interviewer that I can't solve this problem in polynomial : time, but I do want to know the answer if the interviewer can solve it in : polynomial time, so that I can go to Clay Institute and claim their 1 : million dollar prize. : : 讲。
| | | g**e 发帖数: 6127 | 21 lol
【在 g***s 的大作中提到】 : interviewer can solve it as i think. : : polynomial : in
| j***y 发帖数: 2074 | 22 请教一下楼主,这线性规划的数学模型我能理解,毕竟以前在大学里面学过。不过,用
C或者C++有专门的解法或者library吗?
还是要自己手动去求解? | r*******e 发帖数: 7583 | 23 lp_solve package
【在 j***y 的大作中提到】 : 请教一下楼主,这线性规划的数学模型我能理解,毕竟以前在大学里面学过。不过,用 : C或者C++有专门的解法或者library吗? : 还是要自己手动去求解?
| j***y 发帖数: 2074 | | y***m 发帖数: 7027 | 25 ms题意只要求最接近V没要求邮票张数也最少吧? how about this?
邮票数组a,邮票张数数组c
看成 c1*a1 + c2*a2 + c3*a3 ... cn*An >= k,递归a和c求模,一旦找到模为0退出循环
如果要求最少张数就把金额排序再递归
V = 358;
array a[]={0,2,3,5....n}; //邮票金额
array c[]={0,55,13,5,...n}; //邮票张数
array current[]={0,0,0,0,...,n}; //存储当前循环的邮票张数
array pick[]={0,0,0,0,...,n}; //存储最逼近V的邮票张数
calc(V, 1); //算出 pick 数组
int minMod=1000000000000;
function calc(V,j){
int i = V/a[j] > c[j] ? c[j]:V/a[j];
for(;i>-1;i--){
if(i>c[j])
continued;//大于预定的邮票张数继续-1
int imod = V - i*a[j];
current[j] = i;//记录当前邮票张数
//找到最接近V
if( imod == 0 ){
setPickArray(imod);
break;
}
//当前邮票币值满足接近V的先记录下来
if( imod < a[j] && ( i < c[j] ) ){
imod = a[j] - imod;
current[j] = i+1;//记录当前邮票张数
setPickArray(imod);
continued;
}
//如果还有币值,继续递归到下一币值
if( j < a.size() )
calc( imod , j+1 );
//如果到了最后一个币值,记录最接近V的组合合
else
setPickArray(imod);
}
}
function setPickArray(int imod){
if( minMod > imod ){
minMod = imod;
for(int i=0; i < current.size(); i++){
pick[i] = current[i];
current[i] = 0;
}
}
}
讲。
【在 j**l 的大作中提到】 : 我想这题和背包一样是NP的,不知道是否是要用动态规划来解? : 有N种邮票,面值分别为v_1, v_2, ..., v_N, 张数分别为c_1, c_2, ..., c_N。现在 : 要邮寄的包裹需要的邮资是V, 如何选取邮票,使得总面值>=V, 且尽可能的小。 : N, v_1, v_2, ..., v_N, c_1, c_2, ..., c_N都是给定的正整数。
| j***y 发帖数: 2074 | 26 楼上的兄弟,能不能给点注释啊?看不懂啊,尤其是对我这样算法不熟的人。
你这个算法有英文名称吗?
current数组是干啥用的啊?
calc()的功用是什么?两个形参是干啥的呀? | y***m 发帖数: 7027 | 27 注了,其实是从找硬币组合的变种,就是递归求模...
【在 j***y 的大作中提到】 : 楼上的兄弟,能不能给点注释啊?看不懂啊,尤其是对我这样算法不熟的人。 : 你这个算法有英文名称吗? : current数组是干啥用的啊? : calc()的功用是什么?两个形参是干啥的呀?
| g***s 发帖数: 3811 | 28 这个算法的复杂度 O(Nb * V * v_N)
Nb表示硬币的总个数。
m的取发可以用二分,那么可以提高到 O(Nb * V * log v_N)
细节有些可以提高。
估计这个面试官想要的结果。
【在 g***s 的大作中提到】 : assume v1,v2<...: answer = invalid; : m = V + v_n : while ( (t = 背包(m))>=V){ : answer = m; : m = t-1; : } : return answer; : So, we can use 背包 function to solve this problem. :
| j***y 发帖数: 2074 | 29
循环
谢谢添加注释,虽然我还是没怎么看懂。:-(
顺便再问一下,code里面的for循环似乎少一个结尾的花括号。
【在 y***m 的大作中提到】 : ms题意只要求最接近V没要求邮票张数也最少吧? how about this? : 邮票数组a,邮票张数数组c : 看成 c1*a1 + c2*a2 + c3*a3 ... cn*An >= k,递归a和c求模,一旦找到模为0退出循环 : 如果要求最少张数就把金额排序再递归 : V = 358; : array a[]={0,2,3,5....n}; //邮票金额 : array c[]={0,55,13,5,...n}; //邮票张数 : array current[]={0,0,0,0,...,n}; //存储当前循环的邮票张数 : array pick[]={0,0,0,0,...,n}; //存储最逼近V的邮票张数 : calc(V, 1); //算出 pick 数组
| y***m 发帖数: 7027 | 30 呵呵,补上了,时间复杂度?依赖于V,sumA,c..
【在 j***y 的大作中提到】 : : 循环 : 谢谢添加注释,虽然我还是没怎么看懂。:-( : 顺便再问一下,code里面的for循环似乎少一个结尾的花括号。
| | | m***g 发帖数: 90 | 31 弱问这题用多重背包的思路代码怎么写?
谢谢!
这个算法的复杂度 O(Nb * V * v_N)
Nb表示硬币的总个数。
m的取发可以用二分,那么可以提高到 O(Nb * V * log v_N)
细节有些可以提高。
估计这个面试官想要的结果。
【在 g***s 的大作中提到】 : 这个算法的复杂度 O(Nb * V * v_N) : Nb表示硬币的总个数。 : m的取发可以用二分,那么可以提高到 O(Nb * V * log v_N) : 细节有些可以提高。 : 估计这个面试官想要的结果。
| g***s 发帖数: 3811 | 32 Since the DP stores all the values, we don't need to handle (log v_N) times.
So, it is same time complexity of Knapsack problem.
new_V < 2*V
Knapsack can be handle in O(N*V), so this question can be handled in O(N*2*V
) = O(N*V). N is the type of coins.
the O(N*V) codes for knapsack are hard to read. following is sample codes,
time = O(V * sigma log s_i) .
public static int getMinStampNum(Coin[] coins, int V) {
ArrayList p = new ArrayList();
for (Coin coin : coins) {
int value = coin.faceValue;
int num = Math.min(coin.num, V / value + 1);
int g = 1;
while (num > 0) {
int t = Math.min(g, num);
num -= t;
p.add(value * t);
g <<= 1;
}
}
Collections.sort(p);
int newV = getNewV(p, V);
if (p.size() == 1 && p.get(0) >= V) return p.get(0);
int[][] opt = buildBy01Knapsack(p, V + p.get(p.size() - 1) - 1);
for (int i = V; i <= newV; i++) {
if (opt[p.size() - 1][i] >= V) return i;
}
return -1;
}
//simple version, easy to understand, but time complexity is large to
handle this case: (1,1), (2,2), (100000000,10) V=30
private static int getNewV_SimpleVersion(ArrayList p, int V) {
return V + p.get(p.size() - 1) - 1;
}
private static int getNewV(ArrayList p, int V) {
int sum = 0;
for (int i = 0; i < p.size(); i++) {
int value = p.get(i);
if (value >= V) {
if (sum < V) {
//sum of the previous items is less than V, so we just
pick up the current value;
p.clear();
p.add(value);
return value;
}
int pos = sum < value ? i : i + 1;
while (p.size() > pos) p.remove(pos);
return Math.min(sum, value);
}
if (sum < V) sum += p.get(i);
}
return sum;
}
private static int[][] buildBy01Knapsack(ArrayList p, int V) {
int[][] result = new int[p.size()][V + 1];
for (int i = 0; i < result.length; i++)
for (int v = 1; v <= V; v++) {
int value1 = (i == 0) ? 0 : result[i - 1][v];
int value2 = (v >= p.get(i)) ? p.get(i) + ((i == 0) ? 0 :
result[i - 1][v - p.get(i)]) : 0;
result[i][v] = Math.max(value1, value2);
}
return result;
}
static class Coin {
int faceValue;
int num;
Coin(int f, int n) {
faceValue = f;
num = n;
}
}
【在 g***s 的大作中提到】 : 这个算法的复杂度 O(Nb * V * v_N) : Nb表示硬币的总个数。 : m的取发可以用二分,那么可以提高到 O(Nb * V * log v_N) : 细节有些可以提高。 : 估计这个面试官想要的结果。
| g***s 发帖数: 3811 | 33 posted codes just now.
【在 m***g 的大作中提到】 : 弱问这题用多重背包的思路代码怎么写? : 谢谢! : : 这个算法的复杂度 O(Nb * V * v_N) : Nb表示硬币的总个数。 : m的取发可以用二分,那么可以提高到 O(Nb * V * log v_N) : 细节有些可以提高。 : 估计这个面试官想要的结果。
| m***g 发帖数: 90 | 34 太牛了,可是太复杂没大看懂,有形象的图或简单文字描述算法思路和步骤么?
谢谢!
times.
*V
【在 g***s 的大作中提到】 : Since the DP stores all the values, we don't need to handle (log v_N) times. : So, it is same time complexity of Knapsack problem. : new_V < 2*V : Knapsack can be handle in O(N*V), so this question can be handled in O(N*2*V : ) = O(N*V). N is the type of coins. : the O(N*V) codes for knapsack are hard to read. following is sample codes, : time = O(V * sigma log s_i) . : public static int getMinStampNum(Coin[] coins, int V) { : ArrayList p = new ArrayList(); : for (Coin coin : coins) {
| g**e 发帖数: 6127 | 35 先顶再看
times.
*V
【在 g***s 的大作中提到】 : Since the DP stores all the values, we don't need to handle (log v_N) times. : So, it is same time complexity of Knapsack problem. : new_V < 2*V : Knapsack can be handle in O(N*V), so this question can be handled in O(N*2*V : ) = O(N*V). N is the type of coins. : the O(N*V) codes for knapsack are hard to read. following is sample codes, : time = O(V * sigma log s_i) . : public static int getMinStampNum(Coin[] coins, int V) { : ArrayList p = new ArrayList(); : for (Coin coin : coins) {
| m***g 发帖数: 90 | 36 请问这是穷举么?递归效率是否比较低?
余邮票额
【在 y***m 的大作中提到】 : ms题意只要求最接近V没要求邮票张数也最少吧? how about this? : 邮票数组a,邮票张数数组c : 看成 c1*a1 + c2*a2 + c3*a3 ... cn*An >= k,递归a和c求模,一旦找到模为0退出循环 : 如果要求最少张数就把金额排序再递归 : V = 358; : array a[]={0,2,3,5....n}; //邮票金额 : array c[]={0,55,13,5,...n}; //邮票张数 : array current[]={0,0,0,0,...,n}; //存储当前循环的邮票张数 : array pick[]={0,0,0,0,...,n}; //存储最逼近V的邮票张数 : calc(V, 1); //算出 pick 数组
| t******d 发帖数: 15 | 37 let S = v_1*c_1 + v_2*c_2 + ... + v_n*c_n;
if S < V no solution
else let R = S - V
solve the knapsack problem with capacity of R | m***g 发帖数: 90 | 38 没看懂,好像只是重复了一下题目要求么?
【在 t******d 的大作中提到】 : let S = v_1*c_1 + v_2*c_2 + ... + v_n*c_n; : if S < V no solution : else let R = S - V : solve the knapsack problem with capacity of R
| g***s 发帖数: 3811 | 39 这个有问题。反例
(9,2) V=10
S=18
S-V=8
背包得0
【在 m***g 的大作中提到】 : 没看懂,好像只是重复了一下题目要求么?
| t******d 发帖数: 15 | 40
I probably didn't make it clear.
After you solve the knapsack of S-V, that's the stamps you can save.
In your case you save 0 stamps, i.e. you need to use all the stamps
【在 g***s 的大作中提到】 : 这个有问题。反例 : (9,2) V=10 : S=18 : S-V=8 : 背包得0
| | | g***s 发帖数: 3811 | 41 another sample (5,4) 11
S=20
S-V=9
knapsack(9) = 0;
if you pickup all, the sum is 20. but the correct answer is 15.
【在 t******d 的大作中提到】 : : I probably didn't make it clear. : After you solve the knapsack of S-V, that's the stamps you can save. : In your case you save 0 stamps, i.e. you need to use all the stamps
| t******d 发帖数: 15 | 42
As I said, you can save one stamp with 5 face value, which means you need
to use another three stamps.
【在 g***s 的大作中提到】 : another sample (5,4) 11 : S=20 : S-V=9 : knapsack(9) = 0; : if you pickup all, the sum is 20. but the correct answer is 15.
| g***s 发帖数: 3811 | 43 yes. your method is right.
but S could be >> V. some samples:
(1,10000000) 5
(1,1) (2,1) (100000000,1) 5
【在 t******d 的大作中提到】 : : As I said, you can save one stamp with 5 face value, which means you need : to use another three stamps.
| m***g 发帖数: 90 | 44 弱问,背包问题是 2个条件(价值,重量)其中一个是固定的,这题是2个条件(价值
,张数) 都是没限制的,怎么关联到一块?
As I said, you can save one stamp with 5 face value, which means you need
to use another three stamps.
【在 t******d 的大作中提到】 : : As I said, you can save one stamp with 5 face value, which means you need : to use another three stamps.
|
|