0/1 Knapsack问题Linear Space的算法可以实现Backtrack吗? - Programming版 - 未名存档

本页内容为未名空间相应帖子的节选和存档，一周内的贴子最多显示50字，超过一周显示500字访问原贴

Programming版 - 0/1 Knapsack问题Linear Space的算法可以实现Backtrack吗?

相关主题
● 请问一个基本的minimization problem有没有近似解法？ (转载)	● Backtracking search of Boolean satisfy ability
● 算法求教	● Dynamic programming和backtracking有什么区别吗
● 大家帮我回忆一下，以前在这里遇见的一个题目	● Re: 请教一道题目
● 定义的struct数组很大时，为什么会出现奇怪的大数字？	● help on GAMS! thx!!
● 求算法	● MINOS linear programming
● 看了看程序员们的12306方案，真不值配他们那么多钱。	● 求算法:非交子集。琢磨好几天了，特向大家求教。
● 怎么产生全排列？	● 问一个machine learning/SVM 问题
● 能发自学日志么？	● 一个quadratic programming的问题，请指教！

相关话题的讨论汇总
话题: backtrack话题: space话题: knapsack话题: linear话题: 实现

进入Programming版参与讨论

1

(共1页)

b*********n 发帖数: 1258	1 我的理解是要实现Backtrack至少O(n^2) Space Complexity 不知到对不对?
g*****u 发帖数: 298	2 怎么会呢。backtrack解0-1 knapsack 用O(n)空间就够了。每个x_i=0 or 1，用1bit表示就够了。一共有N个，用N bits表示就可以了。
b*********n 发帖数: 1258	3 O(n)可以找到最大的价值总和但是却找不到具体每一件商品是否被pick 我想问的是如果想知道每一件商品是否被pick，是不是只有O(n^2)space的那个算法才可以? 【在 g*****u 的大作中提到】 : 怎么会呢。backtrack解0-1 knapsack 用O(n)空间就够了。 : 每个x_i=0 or 1，用1bit表示就够了。 : 一共有N个，用N bits表示就可以了。

1

(共1页)

进入Programming版参与讨论

相关主题
● 一个quadratic programming的问题，请指教！	● 求算法
● An Bloomberg interview question	● 看了看程序员们的12306方案，真不值配他们那么多钱。
● 让子goodbug 20倍的赌局	● 怎么产生全排列？
● 拜托你们快动手做吧，每人做一个系统，一个测试客户端	● 能发自学日志么？
● 请问一个基本的minimization problem有没有近似解法？ (转载)	● Backtracking search of Boolean satisfy ability
● 算法求教	● Dynamic programming和backtracking有什么区别吗
● 大家帮我回忆一下，以前在这里遇见的一个题目	● Re: 请教一道题目
● 定义的struct数组很大时，为什么会出现奇怪的大数字？	● help on GAMS! thx!!

相关话题的讨论汇总
话题: backtrack话题: space话题: knapsack话题: linear话题: 实现

未名新帖统计// 7月16日

#	版面	帖数(主题数)
-	全站	4871 (796)
1	Military	3777 (569)
2	Stock	341 (51)
3	Joke	117 (17)
4	History	116 (3)
5	Automobile	100 (9)
6	USANews	55 (9)
7	Midlife	45 (1)
8	Headline	41 (41)
9	Dreamer	33 (13)
10	FleaMarket	32 (20)
11	Living	30 (7)

* 这里只显示发帖超过25的版面，努力灌水吧:-)