i*****o
发帖数: 105 | 1 sounds like knapsack variants:
text file is the capacity of letters
each string in the given list consumes some letter
there is no limit on the number of single string
it should use letter set to account capacity and consumption in dp
struct letter_set {
int l[26]; /* count of distinct letters */
} text_file, strings[N];
max{X(text_file - strings[i]) + 1|i=0...N-1} |
|
m*********t
发帖数: 527 | 2 http://community.topcoder.com/stat?c=problem_statement&pm=12928
Snake Snuke has N rectangles cut out of paper. The rectangles are labeled 0
through N-1. You are given int[]s X and Y with N elements each. For each i,
the sides of rectangle i have lengths X[i] and Y[i].
Snake Snuke will choose some of his rectangles and place them onto a table,
one rectangle at a time, in any order he likes. Each rectangle (except for
the first one) must overlap the immediately previous one, so at the end
Snuke wi... 阅读全帖 |
|
r****7
发帖数: 2282 | 3 可是knapsack是NP问题啊。。。哪儿有多项式解法
0
,
, |
|
l*******i
发帖数: 25 | 4 Thanks for the post.
How to solve the 0 subset sum of arbitrary size problem?
Is it the same as the knapsack problem? |
|
m**o
发帖数: 1970 | 5 constraints 的数量 M个 是到时候输入进去的。。可能是1,2,3，。。。n
网上搜来搜去没搜到 最基本的dynamic programming 的 通用方法 - - 不管那些计算
时间 优化什么的
求助！！ |
|
|
|
h*******e
发帖数: 1377 | 8 之前 dp[0...w]是一维的 w 是背包总共可能的最大weight, 现在变成 dp[0...w][0..
.m]
m是你的constraint取背包的最大个数.提示到这吧，之后其他您自己再想想。 |
|
i********m
发帖数: 332 | 9 Knapsack （0/1） 变种，
代码写出来了没跑过 错了一个index
第二天挂了
这算什么难度在电面中？ |
|
f*********5
发帖数: 1237 | 10 Knapsack np hard怎么写？ heuristic? |
|
发帖数: 1 | 11 回溯法就是递归搜索了？再加上DP？416题是特殊knapsack问题或者partition问题，看
上去好像和这个一类，但是416的算法好像在这个题用不上啊。
第二问的意思是，如果这题和416题一类，有没有特殊的解法。因为416针对任意数组，
这个题是特殊的1-N连续整数。 |
|
A***u
发帖数: 3714 | 12 Google了一下，找到一堆List。求大家推荐，最好也有中文的翻译的，这样好教中文。
谢谢
http://www.fairytales.biz/list.html
List of Fairy Tales
A
Adventures of Chanticleer and Partlet
Aged Mother, The
Aladdin and the Wonderful Lamp
Ali Baba and the Forty Thieves
Alice in Wonderland
Angel, The
B
Bearskin
Beauty and the Beast
Beetle who went on his Travels, The
Bell, The
Blue Beard
Blue Light, The
Bright Sun Brings It to Light, The
Brother and Sister
Brother Lustig
C
Caliph ... 阅读全帖 |
|
k****m
发帖数: 4670 | 13 Every French soldier carries a marshal’s baton in his knapsack
没啥不好
可笑吗？ |
|
m*e
发帖数: 1018 | 14 一个月前从楼梯上左脚滑了一跤，接着打了一场球后，左脚跟有些疼，没太在意，以为
慢慢可以恢复，可一个月过去了，才好了六成的样子，单左脚尖可以把自己顶起来但很
吃力。今天仔佃查了下，应该是跟腱炎achilles tendon；期间还是一直在练球，休息
不够，变成像网球肘一样的毛病了。悲惨啊，接下来打球不能跑不能跳了。。。
贴个link,以后网球新人们参考。
http://www.itftennis.com/scienceandmedicine/injury-clinic/tenni
Achilles Tendon
Diagnosis
An injury of the Achilles tendon is a degenerative condition of the tendon,
not an inflammatory process. It is therefore incorrect to describe this as
tendinitis. Tendinopathy is a better term.
The injury is caused by chronic repeti... 阅读全帖 |
|
y***n
发帖数: 30 | 15 好像很多航空公司要求是1个，
不知道2个容不容易混过去。 |
|
|
y***n
发帖数: 30 | 17 好，多谢
1个是登山包，1个事电脑包
打算碰碰运气了，希望不要被拦下。。 |
|
|
|
s**s
发帖数: 404 | 20 拿破仑的原句：Every French soldier carries a marshal's baton in his knapsack. |
|
|
|
|
z**k
发帖数: 945 | 24 拿破仑说：不想当元帅的士兵不是好士兵；
“Every French soldier carries a marshal\'s baton in his knapsack”
孙中山说：人不要立志做大官，要立志做大事 |
|
d*******e
发帖数: 49 | 25 Approximation algorithms for the m-dimensional 0–1 knapsack problem: Worst-ca
se and probabilistic analyses
It is in European Journal of Operational Research 1984.
I can find it on line at science direct.
But I do not have the account to download it.
Please help me download this paper if you have an account.
Thanks! |
|
s***t
发帖数: 113 | 26 to discuss the complexity, the input size should be some *natural*
representation. It is well known that many NP-complete problem can indeed
be solved in polynomial time if some *innatural* representation is used.
For example, Knapsack problem is NP-complete. But it can be solved in
polynomial time
if the max objective is bound above by some value K, i.e., O(K ( poly(n) ).
Here, n
is the number of total available items. |
|
i******t
发帖数: 370 | 27 Guys, you are confused. The number of bottles are integers - this is a
knapsack with integer price/cost. For this problem DP suffices. For the
general problem, you still can use DP to get a pseudo-polynomial algorithm.
1.
i
abou |
|
R*******M
发帖数: 16 | 28 楼主的老板不知道是不是theory圈内人，但感觉楼主对这个community的“习惯”还不甚了解。
knapsack之类的问题是做老了的，我感觉如果不是那种很新的算法，投到SODA上八
成是要被拒的。而且楼主说分析需要case by case，这个如果不是什么特别重要的问题(我指理论上），那么确实被鄙视的可能性比较大。
再说说review，理论的review有些确实挺随便的，无数理论的大牛都在blog上抱怨过了，但这是既成事实，也没法改。只能接受了。自己写review的时候，对得起天地良心就好了。
扫了一下楼主的文章，粗看一下确实不太像theory的paper。应该和当初投SODA什么的，差别比较大了吧。我自己没怎么看过PODC的文章，但SODA看过不少。楼主一开始的那段abstract，还有introduction里的例子，都和theory里的大路文章的风格相差甚远。按照一般做theory的人的脾气，八成会觉得你是圈外人士，不是很了解related work。而且楼主的ref大多引用的是非theory的文章，放到theory里，也会觉得很奇怪。 |
|
c*****t
发帖数: 1879 | 29 google 0-1 knapsack problem. |
|
c*****t
发帖数: 1879 | 30 In the question:
求选取a subset that can minimize the total value, subject to the condition
that total size greater than or equal to B.
So basically, 0-1 knapsack would be finding the largest total size
for a given total value. If this size is greater than B, we are done.
过。 |
|
g*****u
发帖数: 298 | 31 谢谢，和我以前想的一样。不过你有没有觉得，你说的这个knapsack problem的近似解
，比如它的approximation ration是2，但是，原来问题的解其实并没有bounded.
我已经想出一个算法了，不过不是常数级bounded。不过还是谢谢大家！
这个
于A |
|
|
w****h
发帖数: 212 | 33 运行时出线如3452816845 3452816845 3452816845这种奇怪的大数字
以下我本来用的是int,也有类似的错误。不知道哪里来的。
#define C 10000 //define a fixed maximum capacity for the list that can
be taken away of knapsack
#define N 200 //define number of items for the list
struct body { //define a struct with three parts, the item name, size and
value
unsigned int name;
unsigned int size;
unsigned int value;
};
typedef struct body Plist;
void disp(Plist*, unsigned int);
int _tmain(int argc, _TCHAR* argv[])
{
srand((un |
|
b*********n
发帖数: 1258 | 34 我的理解是
要实现Backtrack至少O(n^2) Space Complexity
不知到对不对? |
|
b*********n
发帖数: 1258 | 35 O(n)可以找到最大的价值总和
但是却找不到具体每一件商品是否被pick
我想问的是如果想知道每一件商品是否被pick，
是不是只有O(n^2)space的那个算法才可以? |
|
E*****m
发帖数: 25615 | 36 每堆重量不同嗎？
題意不太清楚。
應該是 Knapsack problem 的變異。 |
|
|
s****u
发帖数: 1433 | 38 呵呵，本人学编程的时候，你估计还是液体呢。
即便是春运最高峰，仍然有火车的某些座位在某些路段遭闲置。
这些都是可以优化减少的。
高大上告诉你，这是标准的多维KNAPSACK问题。好处是可以
分线路解决，变量也有限，不会在乎NP问题。
算了，你个程序员
反正也听不懂。 |
|
h**x
发帖数: 34 | 39
http://en.wikipedia.org/wiki/NP-complete
非常粗略的说，就是算法上只能做到指数级运算时间，而不是多项式运算时间
Boolean satisfiability problem (Sat.)
N-puzzle
Knapsack problem
Hamiltonian path problem
Travelling salesman problem
Subgraph isomorphism problem
Subset sum problem
Clique problem
Vertex cover problem
Independent set problem
Dominating set problem
Graph coloring problem |
|
h**x
发帖数: 34 | 40 麻烦想了解一下诸位在实际工作（比如，金融，生物，工程计算，等领域）中有需要解
决某 NP-complete 问题的吗？
如果有，能否说明一下具体是哪个 NPC problem，以及 problem size 有多大。
谢谢！
http://en.wikipedia.org/wiki/NP-complete
非常粗略的说，就是算法上只能做到指数级运算时间，而不是多项式运算时间
Boolean satisfiability problem (Sat.)
N-puzzle
Knapsack problem
Hamiltonian path problem
Travelling salesman problem
Subgraph isomorphism problem
Subset sum problem
Clique problem
Vertex cover problem
Independent set problem
Dominating set problem
Graph coloring problem |
|
f******k
发帖数: 297 | 41 search for knapsack problem |
|
t**********s
发帖数: 930 | 42 有点象knapsack问题,但我又不知怎么转化成类似的问题:
You are designing a new-and-improved digital video recorder, called NIDVO.
In the NIDVO software, a television show i is represented as a triple: a
channel number ci, a start time si, and an end time ei. The NIDVO owner
inputs a list of n shows to watch and for each show i = 1, 2, ..., n;,
assigns it a pleasure rating ri. Since shows may overlap, and the NIDVO can
record only one show at a time, the NIDVO should record the subset of the
shows that maximize the
aggr |
|
c****n
发帖数: 86 | 43 我们知道其中一个解法就是把所有物品的price/weight比做递减排序，然后一个一个放
进布袋，直到撑破。
有没有人研究过按照其他的函数形式排序，来解这个问题呢？比如，按照(1/weight)，
或者(price-wieght),或者其他的函数形式排序。
怎么证明第一种最好呢，或者莫一种最好呢
多谢！ |
|
c*******h
发帖数: 1096 | 44 无论什么形式排序，只要满足greedy choice property和optimal substructure
property
就能达到最优解 |
|
w******T
发帖数: 71 | 45 Journal of Industrial and Management Optimization
Pages: 847 - 860, Volume: 6 , Issue: 4 , November 2010
Two-person knapsack game
my email: h*********[email protected]
Thanks a lot. |
|
j*****n
发帖数: 1545 | 46 没啥 machine learning 可问的，还是问算法最好。 算法好的人，machine learning
这些东西不会太难, 大部分都是call API， 1个1个试.
可以推1个公式，问1道算法题, knapsack, skytree 之类的， 写1个小code, 40分钟
就够了 |
|
