f******5
发帖数: 11 | 1 //Algorithm DPKnapsack(w[1..n], v[1..n], W)
// var V[0..n,0..W], P[1..n,1..W]: int
// for j := 0 to W do
// V[0,j] := 0
// for i := 0 to n do
// V[i,0] := 0
// for i := 1 to n do
// for j := 1 to W do
// if w[i] j and v[i] + V[i-1,j-w[i]] > V[i-1,j] then
// V[i,j] := v[i] + V[i-1,j-w[i]]; P[i,j] := j-w[i]
// else
// V[i,j] := V[i-1,j]; P[i,j] := j
// return V[n,W] and the optimal subset by ba... 阅读全帖 |
|
X*****r
发帖数: 2521 | 2 【 以下文字转载自 CS 讨论区 】
发信人: Xfilter (支持南开的兄弟们), 信区: CS
标 题: 有对Knapsack问题了解的吗？
发信站: BBS 未名空间站 (Wed Mar 19 11:44:36 2008), 转信
到底multidimensional和multiple knapsack有什么关系？
有没有同时multiple+multidimensional的？有这样的算法吗？
是不是只有branch bound才能达到最优解啊？
多谢了！ |
|
a******h
发帖数: 19 | 3 Anyone know how to modify Knapsack's dynamic programming to use only O(n)
space instead of O(nW) space? |
|
g*****u
发帖数: 298 | 4 怎么会呢。backtrack解0-1 knapsack 用O(n)空间就够了。
每个x_i=0 or 1，用1bit表示就够了。
一共有N个，用N bits表示就可以了。 |
|
A*******r
发帖数: 768 | 5 Kellerer, Hans. et al
Knapsack problems
Berlin ; New York : Springer, c2004. |
|
A*******r
发帖数: 768 | 6 Author: Kellerer, Hans.
Title: Knapsack problems / Hans Kellerer, Ulrich Pferschy, David
Pisinger.
Published: Berlin ; New York : Springer, c2004.
Other Authors/Titles: Pferschy, Ulrich.
Pisinger, D. (David) |
|
S*******e
发帖数: 118 | 7 The 0-1 knapsack can be reduced to this problem when some constraints in
this problem are removed. For each item in the knapsack problem with weight
w and value v, construct w words and v sentences that contain exactly these
w words. Then whether we can cover n sentences with max-weight m is
equivalent to knapsack problem.
The major difference is that w and v need to be integers in this problem,
and w is no larger than a constant. This is exactly the condition where 0-1
knapsack can be solved in... 阅读全帖 |
|
g*****u
发帖数: 298 | 8 我就是从knapsack problem想到这个的。不一样的，knapsack是求最大值，这个求最小
值，knapsack的2-approximation algorithm不能用。其他knapsack的近似解法没看过。 |
|
o******e
发帖数: 1001 | 9 感觉到不是knapsack problem。knapsack problem 是在满足背包容量的情况下求最大
的utility。knapsack problem能转化成graph用动态规划来解。但是把它转化成graph
的时候用的是枚举法。而这个问题只是求满足条件的所有数组。
另外，我觉得这个问题不是一般的动态规划能解得。动态规划的目的是求一个最优解，
而这个问题只是问满足条件的解。如果这个问题时求在sum一定的情况下，找一个组成
这个sum的数的积最大，那么这个问题可能可以用constrained dynamic programming来
解。但是显然，对于面试写code，这是太难了。 |
|
g***s
发帖数: 3811 | 10 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 ... 阅读全帖 |
|
b***e
发帖数: 1419 | 11 来自主题: JobHunting版 - 请问G一题 This can be reduced to the knapsack problem. Concretely, if there’s a
knapsack problem, we can construct n problems following the pattern of this
problem.
1. add 1 0 to the list;
2. add 2 0s to the list;
…, …
n. add n 0s to the list;
If any of the these n problems has a solution, then there is a solution for
the original knapsack problem. |
|
b***e
发帖数: 1419 | 12 来自主题: JobHunting版 - 请问G一题 This can be reduced to the knapsack problem. Concretely, if there’s a
knapsack problem, we can construct n problems following the pattern of this
problem.
1. add 1 0 to the list;
2. add 2 0s to the list;
…, …
n. add n 0s to the list;
If any of the these n problems has a solution, then there is a solution for
the original knapsack problem. |
|
w***g
发帖数: 5958 | 13 这个我不是很在行。rounding technique也是随便想的，给不出reference。但是你这个
问题其实就是knapsack problem。假设所有物品的重量的总和为A，先解重量小于等于A
-B的
knapsack problem。把knapsack problem的解从所有物品中抛掉，剩下的就是你的问题
的解。
过。 |
|
p*******m
发帖数: 20761 | 14
当前用来保护互联网数据所采用的技术主要为代码加密。但是由于量子计算机强大的计
算能力，使其可能在未来的某一天可以找到破解这些加密技术的算法，随之这些加密算
法便变得不再安全。华盛顿州立大学数学学习中心的导师Nathan Hamlin，就正在为这
种未来的可能的不安全做着准备。
Nathan Hamlin 最近将他的一片新的文章发表在了《离散数学开放杂志》（Open
Journal of Discrete Mathematics）上。在这篇文章中，他解释了一段他为博士论文
所写的名为“通用背包编码”（Generalized Knapsack Code）的代码，如何阻止下一
代拥有量子计算机的黑客们的攻击。
这篇文章澄清了对公共秘匙编码这个复杂领域的误解，并且为那些在量子计算时代
终将承担起设计新的互联网安全系统重任的科学家们，提供了一个共同的基本的认知起
点。
Hamil 说“设计安全系统以保护数据，这项工作会涉及来自许多不同领域的专家，
他们的工作方式也会有很多的不同点。所以在某一时刻的工作中可能会包括纯粹的数学
家、应用数学家、计算机程序员和工程师多方的参与。为了实现在现实工作中的... 阅读全帖 |
|
h*****n
发帖数: 188 | 15 来自主题: JobHunting版 - 请问G一题 classic knapsack.
find N/2 numbers to fit in a sum(Array)/2 knapsack. |
|
h*****n
发帖数: 188 | 16 来自主题: JobHunting版 - 请问G一题 classic knapsack.
find N/2 numbers to fit in a sum(Array)/2 knapsack. |
|
c********t
发帖数: 5706 | 17 开始套不进knapsack去，因为把限定的value想当做weight的限制。
后来发现这个限制应该在benefit value上，只要在knapsack中间，比较一下总value是
不是超过limit就行了 |
|
d****m
发帖数: 1008 | 18 我也没明白你的喷点在哪里。也没明白你是喷不是DP还是不是knapsack。
这题是algorithm design 第六章DP的第一个例题，你自己去看。我说是DP入门题不对
？题目我也没仔细看，好像比knapsack还简单些。
也是非常的逗：） |
|
d****m
发帖数: 1008 | 19 我也没明白你的喷点在哪里。也没明白你是喷不是DP还是不是knapsack。
这题是algorithm design 第六章DP的第一个例题，你自己去看。我说是DP入门题不对
？题目我也没仔细看，好像比knapsack还简单些。
也是非常的逗：） |
|
h*****u
发帖数: 109 | 20 有道理。除了guillotine cut，Gilmore and Gomory 还允许 multiple items，但是这
个题目只是允许最多一个。
这个也不属于multi-dimensional knapsack, 因为不是简单的相加关系。
我找到最相关的是：An exact algorithm for general, orthogonal, two-
dimensional knapsack problems, European Journal of Operational Research 83 (
1995) 39-56。但是也不是DP.
感觉如果要表征solution，需要把已经剩余区域的所有极点(extreme points)都记录下
来。如此，怎么设计DP?
o |
|
|
wh
发帖数: 141625 | 22 嗯，我还做过一个影评口头汇报，贴几段在下面，贼长，只要看每段的开头就行，哈哈
。你看过悲情城市吗？说起野狼犬就想起它，不过台湾片mild多得多。日本片有点像西
方片，拷问人性本质之类。又想起人证，哈哈我瞎想。
Stray Dog, in Chinese野良犬, is a Japanese movie by the famous director
Kurosawa, in Chinese 黑澤明. Kurosawa's movies are like most Japanese
masterpieces in that they feature the extremes of human behavior, and reveal
human darkness. This movie, shot in 1949, likewise explores the postwar
mental crisis in the Japanese society.
The dominant impression that runs throughout the movie is heat. It is
s... 阅读全帖 |
|
|
c******t
发帖数: 1500 | 24 floating Knapsack可以用greedy来解
0-1 Knapsack是NP-complete的 |
|
b***e
发帖数: 1419 | 25 来自主题: Programming版 - 算法求教 I believe this is NPC. Here is a reduction to Knapsack:
Given a Knapsack problem as follows:
An array A = {a1, ..., an}, where for each i, ai is a positive integer, find
a subset B of A such that sum(B) = v, where v is a positive interger.
Without
losing generality, we can assume v <= sum(A) / 2;
Let w = sum(A) - 2 * v.
Let A' = A union {w} union Z, where Z = {0, ..., 0} is a set that contains n
+1 0s.
Now if your problem can be solved effectively, then I apply that algorithm
on A' to find out |
|
|
w********9
发帖数: 8613 | 27 这是Shorter Oxford American English Dictionary第五版列出的与德语或者日耳曼语
相关的英语词根或词汇。
-at, suffix2. + -dom, suffix. + -ed, suffix1. + -ed, suffix2. + -en, suffix1
+ -en, suffix2 + -en, suffix5 + -en, suffix6 + -er, suffix1. + -er, suffix3
. + -er, suffix5. + -est, suffix1. + -est, suffix2. + -et, suffix2. + -eth,
suffix1. + -hood, suffix. + -ing, suffix1. + -ing, suffix3. + -ish, suffix1.
+ -kin, suffix. + -le, suffix1 + -le, suffix3 + -less, suffix. + -ling,
suffix1. + -ling, suffix2 + -ly, suffix1. + -ly, s... 阅读全帖 |
|
l******a
发帖数: 3803 | 28 remember the rumbustious 2008 race when the highest
black politician had to give in to the "peer pressure"
to endorse Odumba?
In 2010, he spoke truth, good but too late. still much better
than those stupid zombies that pickaPoo shitpile of chemical waste.
Colin Powell critical of President Obama
By CARRIE BUDOFF BROWN | 9/19/10 12:06 PM EDT Updated: 9/19/10 11:01 PM EDT
Former Secretary of State Colin Powell, who endorsed Democrat Barack Obama
for president in 2008 despite serving three Republic... 阅读全帖 |
|
d**********n
发帖数: 2031 | 29 en.wikipedia.org/wiki/Backpack
A backpack (also called rucksack, knapsack, packsack, pack, or Bergen) is,
in its simplest form, a cloth sack carried on one's back and secured with
two straps that go over the shoulders, but there can be exceptions. Light
weight types of backpacks are sometimes worn on only one shoulder strap. |
|
c****2
发帖数: 3640 | 30 背包问题，理论上是NP-hard，搜Knapsack problem+excel，有好多办法的。 |
|
P**********l
发帖数: 310 | 31 应个景：
Advice for a Young Investigator
Santiago Ramon y Cajal.
Although many would disagree, we believe that the man of science should be
married and should face the pressures and responsibilities of family life
courageously.
He will not emulate the selashness of Epicurus, who did not marry in an
attempt to avoid cares and woes, nor the exaggerated reanement of Napoleon,
whose only use for a woman was a nurse in old age.3 For the man of science,
the aid of a wife is just as necessary in youth as i... 阅读全帖 |
|
w******l
发帖数: 58 | 32 google knapsack problem
个数 |
|
i********r
发帖数: 12113 | 33 this is a 0-1 knapsack problem which has been proved a NP problem. even with
the same unit price. |
|
p*********9
发帖数: 30 | 34 don't know how to output those found numbers. But, all combination can be
found in the arrya B. BTW, it is the 0-1 knapsack problem. The time should
be O(n*sum).
void calculateSum(int[] A, int sum)
{
arrary B[n+1,sum+1];//suppose B has been defined.
for(i=1;i<=n;i++) B[i][0] = 0;
for(i=0;i<=sum;i++) B[0][i] = 0;
for(i=1..n)
{
for(w=0;w<=sum;w++)
{
if( A[i] > w ) B[i,w] = B[i-1, w];
else B[i,w] = max( A[i]+B[i-1,w-A[i]), B[i-1,w]);
}
}
}
with |
|
x***y
发帖数: 633 | 35 Your program is to check whether the prefix of s1 is the string "prefix",
but what that guy said is to check whether the string "prefix" is in the
string "s1".
For the second problem, it's the subset sum problem, a special case of 0-1
knapsack problem and you can find the subset by tracing back the table...
It's pseudo-polynomial algorithm, which runs as O(n*Sum), where n is the length of
a...Tracing back table cost O(n) time...
//below just my program, probably not the best
//the key part of it |
|
f*********r
发帖数: 68 | 36 Knapsack runs in O(nW), where n is the # of items, and W is the weight. If W
=O(n), then it's polynominal, but what if W=O(2^n)??? So in general case it
is NPC. |
|
g*******y
发帖数: 1930 | 37 yes, it's NPC
set partition
正号和符号其实就是对数组的一个partition，F等于0，就是要求partition的两个subset相等。这不就是NPC了嘛。
可以用knapsack类似的DP，或者用backtracking的方法做。
1 |
|
g*******y
发帖数: 1930 | 38 就是跟knapsack类似的方法啊。
伪多项式算法。
bool state[i][j] = whether you can find a subset from A[1...i] that sums to
j;
i<=N;
j<=Total_Sum/2
state[i][j] = state[i-1][j-A[i]] || state[i-1][j] |
|
|
a****n
发帖数: 1887 | 40 DP可以压缩空间
0-1和完全背包压缩方法不一样 |
|
b*********n
发帖数: 1258 | 41 我的理解是
要实现Backtrack至少O(n^2) Space Complexity
不知到对不对? |
|
|
b*********n
发帖数: 1258 | 43 O(n)可以找到最大的价值总和
但是却找不到具体每一件商品是否被pick
我想问的是如果想知道每一件商品是否被pick，
是不是只有O(n^2)space的那个算法才可以? |
|
m*****f
发帖数: 1243 | 44 say a1, a2, a3, ....an:
compute the sum one by one and list them as a new list
a1, a1+a2, a1+a2+a3, a1+a2+a3+a4,.....,a1+....+an,
this will take O(n).
now the question becomes find two numbers a, b in this new list, that
a - b = that particular number, which is a typical 2sum problem solved
in O(n)
Possible follow-up: if the word "consequtive" is removed, then it becomes a
0/1 knapsack problem, could be solved by dp. |
|
r****o
发帖数: 1950 | 45 那不就是任意几个数的和等于15吗？
加法跟consecutive没关系吧？
0-1 knapsack? |
|
r****o
发帖数: 1950 | 46 没看明白，我怎么觉得这个问题就是0-1 knapsack啊？
1
one
get
= |
|
b***e
发帖数: 1419 | 47 明显不行.
If there exists a polynomial procedure for this problem, then I can
applied this procedure with binary search to solve knapsack problem in
polynomial time. |
|
n******r
发帖数: 1247 | 48 Nice exercise for practising Knapsack problem
Let all items having weight 1, i.e. w_i=1, p_i being item i's value, A(Y)
being the min weight that can be achieved with total money Y (achieveable
becasue 1 is always there)
Then
A(0) = 0
A(Y)=min{1+A(Y-p_i)|p_i≤Y}
Calculate A(1),A(2),..., till you get A(80)
What kind of position is this interview for?
10 |
|
|
