Here's the classic backpack
question(https://www.lintcode.com/problem/backpack/description):
Given n items with size Ai, an integer m denotes the size of a backpack.
How full you can fill this backpack?
Using classic DP with memoize to solve this problem in Racket would be ps1.
I would like to try to solve this problem in HtDP-y way, since lintcode
doesn't support Racket-lang, I use python to implement (refer: ps2).
lintcode told me that my python implementation is OOM, I was wondering if
maybe the `fn_for_n` and `fn_for_lon` is not the right hammer for this nail?
========ps1 here ===========
#lang racket
(require rackunit)
(struct obj (value weight))
(struct node (value weight paths))
(define (max-value objs max-weight)
(if (null? objs)
0
(match-let (((list-rest (struct obj (value weight)) rest) objs))
(if (> weight max-weight)
(max-value rest max-weight)
(max (+ value (max-value rest (- max-weight weight)))
(max-value rest max-weight))))))
(define allcalls 0)
(define memcalls 0)
(define (memoize f)
(let ((cache (make-hash)))
(λ args
(set! allcalls (add1 allcalls))
(hash-ref! cache args
(thunk
(set! memcalls (add1 memcalls))
(apply f args))))))
(set! max-value (memoize max-value))
(define (max-value/nomem objs max-weight)
(if (null? objs)
0
(match-let (((list-rest (struct obj (value weight)) rest) objs))
(if (> weight max-weight)
(max-value/nomem rest max-weight)
(max (+ value (max-value/nomem rest (- max-weight weight)))
(max-value/nomem rest max-weight))))))
;; (o->node (obj 400 2))
;; ==> (node 400 2 (list (obj 400 2)))
(define (o->node item)
(node (obj-value item) (obj-weight item) (list item)))
(define (n-eq=? n1 n2)
(and (= (node-value n1) (node-value n2))
(= (node-weight n1) (node-weight n2))))
;; lon: node list.'((node 200 7 ((obj 200 7))) (node 200 3 ((obj 200 3)))
(node 300 5 ((obj 300 5))))
;; W: weight
;; cur: node. (node 400 10 (list (obj 200 3) (obj 200 7)))
;; => list of node
;; (graph-nbs ex (node 200 3 (list (obj 200 3))) 10) =>
;; '((node 500 8 (list (obj 300 5) (obj 200 3))))
(define (graph-nbs lon cur W)
(let* ([head-cur (first (node-paths cur))] ; (obj 200 3)
[rest-item (rest (member (o->node head-cur) lon n-eq=?))])
(filter (λ (ncur)
(>= W (node-weight ncur)))
(map (λ (ncur) ;; ncur:(5 300 ((banana 5 300)))
(node (+ (node-value ncur) (node-value cur))
(+ (node-weight ncur) (node-weight cur))
(cons (first (node-paths ncur)) (node-paths
cur))))
rest-item))))
;; loi: ITEM list defined as above. ex. (list (obj 200 7) (obj 200 3) (obj
300 5))
;; W: weight
;; (ini-todo h1 10)
;; => (list (node 200 7 (list (obj 200 7)))
;; (node 200 3 (list (obj 200 3)))
;; (node 300 5 (list (obj 300 5))))
(define (ini-todo loi W)
(map
o->node
(filter (λ (item)
(<= (obj-weight item) W))
loi)))
(define (knapsack loi W)
(let ([loc (ini-todo loi W)])
(define (fn-for-n cur todo acc)
(let* ([nbs (graph-nbs loc cur W)]
[nacc (if (> (node-value cur) (node-value acc))
cur
acc)])
(if (empty? nbs)
(fn-for-lon todo nacc)
(fn-for-lon (append nbs todo) nacc))))
(define (fn-for-lon todo acc)
(if (empty? todo)
(node-value acc)
(fn-for-n (first todo) (rest todo) acc)))
(fn-for-lon loc (node 0 0 (list)))))
(define h1 (list (obj 2 2)))
(check-equal? (node-value (knapsack h1 2)) 2)
(check-equal? (node-value (knapsack h1 1)) 0)
(define h2 (list (obj 2 2) (obj 1 1) (obj 3 3)))
(check-equal? (node-value (knapsack h2 6)) 6)
(check-equal? (node-value (knapsack h2 5)) 5)
(define h3 (list (obj 10 5) (obj 30 6) (obj 40 4) (obj 50 3)))
(check-equal? (node-value (knapsack h3 10)) 90)
(define h4 (list (obj 4 12) (obj 2 1) (obj 10 4) (obj 2 2) (obj 1 1)))
(check-equal? (node-value (knapsack h4 15)) 15)
(define (gen-objs n)
(if (zero? n)
'()
(cons (obj (random 250 300) (random 100 200)) (gen-objs (sub1 n)))))
(define N 50)
(define testing-objs (gen-objs N))
(displayln "Memoize: ")
(time (max-value testing-objs (* 150 N)))
#|
(displayln "")
(displayln "No mem: ")
(time (max-value/nomem testing-objs (* 150 N)))
(displayln "")
(displayln "HtDP")
(time (knapsack testing-objs (* 150 N)))
|#
=======ps2 here===============
class Solution:
"""
@param m: An integer m denotes the size of a backpack, 11
@param A: Given n items with size A[i], [2, 3, 5, 7]
@return: The maximum size
"""
def backPack(self, m, A):
A.sort()
todo = []
acc = 0
for i in range(len(A)):
tmp = (i, A[i])
todo.append(tmp)
return self.fn_for_lon(todo, 0, A, m)
def fn_for_lon(self, todo, acc, Arr, target):
#print "Entering fn_for_lon, todo:%s, acc:%s\n" % (str(todo),
str(acc))
if not todo:
return acc
cur = todo[0]
rest = todo[1:]
return self.fn_for_n(cur, rest, acc, Arr, target)
def fn_for_n(self, cur, todo, acc, Arr, target):
#print "Entering fn_for_n, cur:%s, todo:%s, acc:%s\n" % (str(cur),
str(todo), str(acc))
if acc == target:
return target
cur_sum = cur[1]
if acc < cur_sum <= target:
acc = cur_sum
nbs = self.get_next(cur, Arr, target)
todo = todo + nbs
return self.fn_for_lon(todo, acc, Arr, target)
def get_next(self, cur, Arr, target):
res = []
for i in range(cur[0]+1, len(Arr)):
new_acc = cur[1] + Arr[i]
if new_acc <= target:
res.append((i, new_acc))
return res
if __name__ == '__main__':
sol = Solution()
# A1 = [2,3,5,7]
# t1 = 11
# nbs1 = sol.get_next((0,A1[0]), A1, t1)
# print "get nbs of A:%s is %s\n" % (str(A1), str(nbs1))
# bp1 = sol.backPack(t1, A1)
# print "get bp of A:%s is %d\n" % (str(A1), bp1)
A2 = [3,4,8,5]
t2 = 10
# A2.sort()
# nbs2 = sol.get_next((0,A2[0]), A2, t2)
# print "get nbs of A:%s is %s\n" % (str(A2), str(nbs2))
bp2 = sol.backPack(t2, A2)
print "get bp of A:%s is %d\n" % (str(A2), bp2)
--
You received this message because you are subscribed to the Google Groups
"Racket Users" group.
To unsubscribe from this group and stop receiving emails from it, send an email
to racket-users+unsubscr...@googlegroups.com.
For more options, visit https://groups.google.com/d/optout.
