python_de_pcc/knapsack4.py at master · letusfly85/python_de_pcc · GitHub

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
# -*- coding: utf-8 -*-

Num = 4
Wei = 5

W = [2, 1, 3, 2]
V = [3, 2, 4, 2]

w = len(W)
v = len(V)

ANCHOR = 9999999999
memsets = {}

def initialize_memsets():
    for i in range(0, w * v + 1):
        memsets[i] = {}
        for j in range(0, w * v + 1):
            memsets[i][j] = ANCHOR

    memsets[0][0] = 0

def solve():
    for i in range(0, Num):
        for j in range(0, w * v):
            if (j < V[i]):
                memsets[i+1][j] = memsets[i][j]
            else:
                memsets[i+1][j] = min(memsets[i][j], memsets[i][j-V[i]] + W[i])

    res = 0
    for i in range(0, w * v):
        if (memsets[Num][i] <= Wei):
            res = i

    print res

def __main__():
    initialize_memsets()
    solve()

__main__()