0-1 Knapsack Solution with Dynamic Programming

I've just written a program to solve Single Knapsack Problem with Dynamic Programming via python. I know my solution is not much pythonic, because of I had a rush a little bit. So, please don't hesitate to contact with me to propose more pythonic way.

def giveAsMatrix(f, counter):
    tmpList = []
    f.seek(0)
    for k in xrange(0, counter):
        tmpList.append(f.readline().strip().split('\t'))
    return tmpList

Above function returns a str list from a file.

import numpy as np
def convertInt(myChar, counter):
    tmpList = np.zeros((counter, 2), dtype=np.uint16)
    for i in xrange(0, counter):
        tmpstr = myChar[i][0]
        tmpstr = tmpstr.strip().split(' ')
        if(len(tmpstr) == 2):
            tmpList[i][0] = long(tmpstr[0])
            tmpList[i][1] = long(tmpstr[1])
        elif(len(tmpstr) == 3):
            tmpList[i][0] = long(tmpstr[0])
            tmpList[i][1] = long(tmpstr[2])
    return tmpList

convertInt function will return an unsigned integer list from my str list.

def sortbyWeight(weights, values):
    for i in xrange(0, len(weights)):
        for j in xrange(0, len(weights)-1):
            if weights[j] > weights[j+1]:
                temp_w = weights[j+1]
                temp_v = values[j+1]
                weights[j+1] = weights[j]
                values[j+1] = values[j]
                weights[j] = temp_w
                values[j] = temp_v
    return weights, values

After I sorted by weight I get better result than before.

def pytKnapsack(n, cap, items):
    i = 0
    bestvalues = np.zeros((len(items)+1, cap+1), dtype=np.long)
    for i, (value, weight) in enumerate(items):
        i += 1
        for capacity in xrange(cap + 1):
            if weight > capacity:
                bestvalues[i][capacity] = bestvalues[i - 1][capacity]
            else:
                candidate1 = bestvalues[i - 1][capacity]
                candidate2 = bestvalues[i - 1][capacity - weight] + value
                bestvalues[i][capacity] = max(candidate1, candidate2)
    reconstruction = []
    i = n
    j = cap
    while i >= 0:
        if bestvalues[i][j] != bestvalues[i - 1][j]:
            reconstruction.append(items[i - 1])
            j -= items[i - 1][1]
        i -= 1
    reconstruction.reverse()
    return bestvalues[len(items)][cap], reconstruction

Knapsack solution in above function whose name is pytKnapsack. It takes 3 arguments n is total number of values and weights, cap is max capacity and items is a list which consist of values and weights.

import os
os.chdir(your_files_directory)
with open(m_file) as f:
    counter = len(f.readlines())
    myChar = giveAsMatrix(f, counter)
    myChar = convertInt(myChar, counter)
    #according to my data set for the first row, 
    #first values is my number of value and second value is my capacity
    n = int(myChar[0][0])
    k = myChar[0][1]
    values = np.zeros((n))
    weights = np.zeros((n))
    for i in xrange(1, counter):
        values[i-1] = myChar[i][0]
        weights[i-1] = myChar[i][1]
    unsorted = concatenate_list(values, weights)
    weights, values = sortbyWeight(weights, values)
    items = concatenate_list(values, weights)
    obj, last_arrays = pytKnapsack(counter-1, k, items)
    result = np.zeros((n), dtype=np.long)
    for i in xrange(0, len(unsorted)):
        for j in xrange(0, len(last_arrays)):
            if unsorted[i][0] == last_arrays[j][0] and unsorted[i][1] == last_arrays[j][1]:
                result[i] = 1
    print obj
    for i in xrange(0, len(result)):
        print result[i],

When you run your input and output should be like below: