-
Notifications
You must be signed in to change notification settings - Fork 56
Expand file tree
/
Copy pathKnapsack.py
More file actions
64 lines (50 loc) · 2.05 KB
/
Knapsack.py
File metadata and controls
64 lines (50 loc) · 2.05 KB
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
# -*- coding: utf-8 -*-
"""
Problem Statement
Given a list of n integers, A={a1,a2,…,an}, and another integer, k representing the expected sum. Select zero or more
numbers from A such that the sum of these numbers is as near as possible, but not exceeding, to the expected sum (k).
Note
Each element of A can be selected multiple times.
If no element is selected then the sum is 0.
Input Format
The first line contains T the number of test cases.
Each test case comprises of two lines. First line contains two integers, n k, representing the length of list A and
expected sum, respectively. Second line consists of n space separated integers, a1,a2,…,an, representing the elements of
list A.
"""
__author__ = 'Danyang'
class Solution(object):
def solve(self, cipher):
"""
repeatable knapsack, dp
f[i][c] represents the max possible value at the index i given the capacity c
normally:
f[i][c] = max{f[i-1][c], f[i-1][c-w_i]+v_i}
since repeatable:
f[i][c] = max{f[i-1][c], f[i-1][c-w_i]+v_i, f[i][c-w_i]+v_i}
since f[i][c] represent the max possible value at i, c; thus only need to consider f[i-1][c-w_i] among others
:param cipher: the cipher
"""
n, k, A = cipher
f = [[0 for _ in xrange(k + 1)] for _ in xrange(n + 1)] # f[0, :] is dummies
for i in xrange(n + 1):
for c in xrange(k + 1):
f[i][c] = f[i - 1][c]
temp = c - A[i - 1]
if temp >= 0:
f[i][c] = max(f[i - 1][c], f[i - 1][c - A[i - 1]] + A[i - 1], f[i][c - A[i - 1]] + A[i - 1])
return f[n][k]
if __name__ == "__main__":
import sys
f = open("0.in", "r")
# f = sys.stdin
solution = Solution()
testcases = int(f.readline().strip())
for t in xrange(testcases):
# construct cipher
n, k = map(int, f.readline().strip().split(' '))
A = map(int, f.readline().strip().split(' '))
cipher = n, k, A
# solve
s = "%s\n" % (solution.solve(cipher))
print s,