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.
|
|
