g*****u
发帖数: 298 | 1 设3个壶每按一次分别由upper和lower bound
u1, l1
u2, l2
u3, l3
两个容量的bound B1和B2
设每个壶要按x_i次，
则这就是一个integer programming问题，更确切的来说就是一个un-bounded knapsack |
|
s*****g
发帖数: 5159 | 2 ONLINE, best effort solution
assume r spaces are left in the cup, f space has to be filled to reach the r
equirement
assume
large is L +/- l
medium is M +/-m
small is S +/-s
pick the smallest cup X such that X - x is larger than f and X + x is smalle
r than r, if there exists no such option,
find pick the largest cup X such that X + x is less than r
However, if the problem has to be done OFFLINE and a solution has to guarant
teed, then the problem is NP hard from a reduction of knapsack problem, |
|
i*****r
发帖数: 265 | 3 来自主题: JobHunting版 - 问道编程题 Isn't it NP-complete? Knapsack? |
|
b********h
发帖数: 119 | 4 这个问题跟经典的knapsack问题很像。从两个维度上可以减小问题的规模；一个是sum
的大小，另一个是数组的大小。对于给定的sum和数组，可以考虑数组里的每一个元素a
[i]。要么a[i]被选中，要么不被选中。如果a[i]被选中,那么答案就是剩下的数组元素
有多少种组合能生成sum-a[i]。反之，答案就是剩下的数组元素有多少种组合能生成
sum。 |
|
y*c
发帖数: 904 | 5
我做过two constraint 0-1 knapsack跟one dimension 解法类似。多重背包不知道一
样不一样。 |
|
P********l
发帖数: 452 | 6 knapsack won't work because the weights of later sentences depend on the
previous words collected.
it seems can be solved by linear programming. but I don't know how to setup
the equations now. |
|
c******n
发帖数: 4965 | 7 不对吧， knapsack 里面的weight 都是有同样意义的。
这里的3-word sentence 可以是abc, or def, 当然是不一样的了
constraints in
weight
exactly these
problem,
where 0-1
http://en.wikipedia.org/wiki/Knapsack_problem, section "Dynamic
programming solution".
minor
problem). |
|
g***s
发帖数: 3811 | 8 "In computer science, the subset sum problem is an important problem in
complexity theory and cryptography. The problem is this: given a set of
integers, does the sum of some non-empty subset equal exactly zero? For
example, given the set { −7, −3, −2, 5, 8}, the answer is
yes because
the subset { −3, −2, 5} sums to zero. The problem is NP-complete.
An equivalent problem is this: given a set of integers and an integer s,
does any non-empty subset sum to s? Subset su... 阅读全帖 |
|
j**l
发帖数: 2911 | 9 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), 面试官那里肯定几乎不得分了。 |
|
t******d
发帖数: 15 | 10 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 |
|
t******d
发帖数: 15 | 11
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
发帖数: 3811 | 12 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
发帖数: 1782 | 13
classical but no idea.
classical
merge? classical
classical
i)
sounds like a knapsack problem.
each product p has a count c(p)? then min_heap, classical. |
|
s****j
发帖数: 67 | 14 i think only O(n^2*k) is needed to solve this problem using a dp method,
similar to knapsack problem |
|
P***P
发帖数: 1387 | 15 先求总和 = x, 然后找n个元素使其和约为x/2, 剩下的就是Knapsack problem了
当然这个肯定不是最优的 |
|
|
J***e
发帖数: 50 | 17 COV (calculus of variation)
KS (knapsack problem) |
|
l*********8
发帖数: 4642 | 18 1. BST Optimal Binary Search Tree Problem
2. COV Optimal Covering problem
3. ILP integer linear programming
4. KS Knapsack Problem
5. LCS Longest Common Subsequences
6. LSP Longest Simple path Problem
7. MCM Matrix chain multiplication
8. ODP Optimal Distribution Problem
9. SCP Stagecoach Problem
10. SPA Shortest Path in a Acyclic graph
11. SPC Shortest Path in a Cyclic graph
12. TSP Travelling salesman problem |
|
Z*****Z
发帖数: 723 | 19 把所有硬币放在一个数组c里面。然后函数F[i,j]代表用前i个硬币摆出value j的摆法。
初始F[*,*] = 0
然后F[i,j] = sum(F[i-1, j - k * c[i]]) 0 <= k <= j/c[i]
实现起来可以用背包九讲里面第二讲的方法：
F[i,j] = F[i, j - c[i]] + F[i-1, j]
代码：
package common.knapsack;
public class Complete {
public static void main(String[] args) {
int[] in = {1, 5, 10, 25};
System.out.println(howMany(in, 11));
}
//How many ways to pack
public static int howMany(int[] arr, int n){
... 阅读全帖 |
|
b***e
发帖数: 1419 | 20 This is equivalent to partition or knapsack. |
|
b***e
发帖数: 1419 | 21 Assuming you have 2*n items, the sum of which is S. Then you can add
2000000 * n items, each of which is of value S/4. This way you are pretty
much bound to divide the S into two halfs, which is a partition/knapsack
problem. |
|
z*****b
发帖数: 1016 | 22 3.一个仓库, 可以sell product in regular price,也可以sale in lower price,怎么
决定多少产品sell,多少产品sale之类的.
请问下面问题怎么解？
看上去像knapsack problem, 仓库的空间有限，存放的物品数量有限，价格不同，然后
来max收益？？
请指教~~thanks |
|
z*****b
发帖数: 1016 | 23 3.一个仓库, 可以sell product in regular price,也可以sale in lower price,怎么
决定多少产品sell,多少产品sale之类的.
请问下面问题怎么解？
看上去像knapsack problem, 仓库的空间有限，存放的物品数量有限，价格不同，然后
来max收益？？
请指教~~thanks |
|
b*******e
发帖数: 217 | 24 来自主题: JobHunting版 - 请问G一题 DP problem: knapsack
Recursive formulation:
Exist(i, j, k) = Exist(i-1, j, k) || Exist(i-1, j-Xi, k-1)
Where i is the index of ith element, j is the sum targeted, and k is the
number of elements selected to get the j and Xi is the value of the ith
element.
We need to decide whether any Exist(n, j, n/2) is true for j = X0, X0+1, ...
n/2.
For all j where Exist(n, j, n/2) == true, pick the j which is closest to Sum
(n) / 2. ------(3)
Then, Abs(Sum(n) /2 - j - j) is the smallest delta of the two su... 阅读全帖 |
|
b*******e
发帖数: 217 | 25 来自主题: JobHunting版 - 请问G一题 DP problem: knapsack
Recursive formulation:
Exist(i, j, k) = Exist(i-1, j, k) || Exist(i-1, j-Xi, k-1)
Where i is the index of ith element, j is the sum targeted, and k is the
number of elements selected to get the j and Xi is the value of the ith
element.
We need to decide whether any Exist(n, j, n/2) is true for j = X0, X0+1, ...
n/2.
For all j where Exist(n, j, n/2) == true, pick the j which is closest to Sum
(n) / 2. ------(3)
Then, Abs(Sum(n) /2 - j - j) is the smallest delta of the two su... 阅读全帖 |
|
n*****s
发帖数: 6495 | 26 knapsack吧
2个dependency变成1个就行 O(mS) |
|
c********t
发帖数: 5706 | 27 唉，好像还是有问题，感觉这道题套不进knapsack |
|
e****e
发帖数: 418 | 28 The idea is to explore all the combinations of weights array by masking and
bit shifting.
i.e. v1=5 w1=3, v2=3 w2=2, v3=4 w3=1, we form the two arrays as follows:
values[5, 3, 4], weights[3, 2, 1], W = 5.
for weights array[3, 2, 1], we want the all subsets of the elements.
such as:
[](no element)
[1]
[2]
[3]
[1 2]
[1 3]
[2 3]
[1 2 3]
We can get this subsets by masking bit by bit if we think of the array
bitwise.
[3 2 1]
0 0 0 -> (no element)
0 0 1 -> [1]
0 1 0 -> [2]
1 0 0 -> [3]
1 0 1 ... 阅读全帖 |
|
x*******6
发帖数: 262 | 29 这题不是一种knapsack问题么，
类似combination的解法 |
|
c*****a
发帖数: 808 | 30 年轻版林青霞啊
印象中就东方不败
我昨天开始学dp...
计划:
LIS,Longest common sub-sequence, longest common substring, edit distance,
shortest distance in graph, chain matrix multiplication, subset sum, 0/1/
knapsack, travelling salesman
才做了前3题 |
|
d****m
发帖数: 1008 | 31 第二题不是教科书上的经典knapsack problem吗。。。DP入门题。。 |
|
n*********r
发帖数: 24 | 32 有人提到用Knapsack DP的方法解。可是，在面试的时候，我说想用DP的方法来考虑这
个问题的时候，直接就被打断，说dynamic programming不正确。 |
|
d****m
发帖数: 1008 | 33 第二题不是教科书上的经典knapsack problem吗。。。DP入门题。。 |
|
n*********r
发帖数: 24 | 34 有人提到用Knapsack DP的方法解。可是，在面试的时候，我说想用DP的方法来考虑这
个问题的时候，直接就被打断，说dynamic programming不正确。 |
|
|
s******s
发帖数: 31 | 36 个人看法，每个餐馆都用dp算最便宜的买法。就是n-d weighted knapsnack。如果一共
有n种菜，那建立一个n-dimensional matrix。每个dimension对应一道菜。每个
dimension的index是一道菜的数量。matrix的值是能买到的最低的价格。与一般
knapsack不同之处是需要处理多买的情况。今天没时间写code，你可以先看看类似的题
，希望对你有帮助。 |
|
|
|
I**********s
发帖数: 441 | 39 这些是我以前做研究时一个项目涉及到的常见的DP问题. 我为了资料全面起见加上了,
但多数不会见于面试.
BST Optimal Binary Search Tree Problem
COV Optimal Covering Problem
ILP Integer Linear Programming Problem
KS01 0/1 Knapsack Problem
LCS Longest Common Subsequence Problem
LSP Longest Simple Path Problem
MCM Matrix Chain Multiplication Problem
ODP Optimal Distribution Problem
RAP Production: Reject Allowances Problem
SCP Stagecoach Problem
SPA Shortest Path in an Acyclic Graph Problem
SPC Shortest Path in an Cyclic Graph Problem
TSP Traveling S... 阅读全帖 |
|
|
l******6
发帖数: 340 | 41 问一道题～
2D knapsack
class rect{
public:
int width;
int height;
int area;
};
input: vector source , int canvasWidth , int canvasHeight
no overlap allowed , no rotate allowed, each rect int source and be used as
many times as
possible (area = width * height , setting area as another val will be a
similar problem)
compute the max coverage of canvas using the rects int the source
a dp solution
maxCover[row][col] = max (maxCover[subRow][col] + maxCover... 阅读全帖 |
|
|
w*******s
发帖数: 138 | 43 这个paper里的方法有一个额外的约束：
This cutting problem allows only recursive side-to-side or guillotine cuts o
f the knapsack.
就是说必须从一边割到另外一边（不能割到中间就停），原题里没有这个约束。 |
|
j******1
发帖数: 25 | 44 回报本版，新鲜G的电面面经，顺便求bless。
(1) Suppose each request has some data, calculate the average bandwidth in
the last 1 second, 1minute, 1 hour.
这题跟careercup那道recent average request很像。
首先，不能有错误，只想出来了use a queue as moving window, and then take
average over last 1 sec, 1 minute, 1 hour. Maintain the queue by deleting
all requests information outside the 1 hour window.
其次，允许一定的错误量。这样就可以用circular array. For example, take a
circular array to store the bandwidth in each second, sample_per_sec[3600].
Then circul... 阅读全帖 |
|
s****g
发帖数: 43 | 45 小朋友去露营。老师发了一个要带的东西的单子。运动器材店的东西是打包卖的，每包
东西的组合不同，价格也不同。求以最少的钱把要的东西都买下来。
有点像换硬币最少方式(or knapsack variation?)，可是没能找出动态公式来。 |
|
f*****g
发帖数: 887 | 46 如果DFS的话，复杂度是m!个knapsack problem吧 |
|
f*****g
发帖数: 887 | 47 如果DFS的话，复杂度是m!个knapsack problem吧 |
|
|
f*********0
发帖数: 17 | 49 写了个dp的方法：
dp[i] 表示用i个point最多能买到的cash。复杂度是O(拥有的point数 * 物品数)。
这个和背包问题完全一样啊。
Reply wsnmn, 注意这里使用point买cash，不是用cash买point。
int knapsack(vector &cash, vector &point) {
int dp[859] = {0};
int n = cash.size();
for (int i = 1; i <= 858; ++i) {
for (int j = 0; j < n; ++j) {
if (i-point[j] >=0) {
dp[i] = max(dp[i], dp[i-point[j]]+cash[j]);
}
}
}
return dp[858];
} |
|
|
