KnapsackProblem.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<center> \n",
    "    <h1>\n",
    "Linear and Quadratic Knapsack Problem\n",
    "    </h1>\n",
    "    <h2>\n",
    "Large Scale Optimization for Data Science\n",
    "    </h2>\n",
    "    <h3>\n",
    "Kale-ab Tessera, 1973752\n",
    "    </h3>\n",
    "</center>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "In the Knapsack problem, our goal is to find the optimal combination of objects which are bound by a total weight W and which achieve the highest profit / value (v). The problem can be applied to various real life applications such as the resource allocation problem.\n",
    "\n",
    "Two variants of the Knapsack problem are considered. The **Linear Knapsack Problem**, where items have individual weights and values, and the **Quadratic Knapsack Problem** where there is an additional term in the objective functions, which represents the extra profit gained from choosing a particular combination of items (in our case pairs). "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Problem 1 - Linear Knapsack Problem"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Linear Implementation of Knapsack Problem.\n",
    "<br/> $$( v_i , w_i) = \\{ (2,7),(6,3),(8,3),(7,5),(3,4),(4,7),(6,5),\n",
    "(5,4),(10,15),(9,10),(8,17),(11,3),(12,6),(15,11),(6,6),\n",
    "(8,14),(13,4),(14,8), $$ <br/>\n",
    "$$ (15,9),(16,10),(13,14),(14,17),(15,9),(26,24),(13,11),(9,17),(25,12),(26,14) \\}$$ with **total capacity W = 30**"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 1.1 Greedy Implementation"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [],
   "source": [
    "import numpy as np\n",
    "\n",
    "# Calculate Score - v_i/w_i\n",
    "def calculateScore(v,w,n):\n",
    "    score = np.array([])\n",
    "    for i in range(n):\n",
    "        score = np.append(score,round((v[i]/w[i]),3)) \n",
    "    scoreIndexs = np.argsort(-score)\n",
    "    \n",
    "    return scoreIndexs\n",
    "\n",
    "def linearKnapSack(v,w,n,W,shouldPrint=False):\n",
    "    sumItemsInKnapsack = 0\n",
    "    \n",
    "    #Sort items according to their score\n",
    "    scoreIndexs =  calculateScore(v,w,n)\n",
    "    indexofElementsInKnapsack = np.zeros(n).astype(int)\n",
    "    \n",
    "    # Add item with highest score, that is below capacity W.\n",
    "    for i in range(n):\n",
    "       indexOfLargestElement = scoreIndexs[i]\n",
    "       if((sumItemsInKnapsack+w[indexOfLargestElement]) <= W ):\n",
    "           indexofElementsInKnapsack[indexOfLargestElement] = 1 \n",
    "           sumItemsInKnapsack += w[indexOfLargestElement]\n",
    "           if(shouldPrint):\n",
    "               print(\"Adding (\",v[indexOfLargestElement],\",\",w[indexOfLargestElement], \n",
    "                     \") to the knapsack\")    \n",
    "    \n",
    "    if(shouldPrint):\n",
    "        print(\"***************************\")\n",
    "        print(\"Arrays: \")\n",
    "        print(\"v_i = {0}\".format(v))\n",
    "        print(\"w_i = {0}\".format(w))\n",
    "        print(\"x_i = {0}\".format(indexofElementsInKnapsack))\n",
    "    \n",
    "    #Return index of set that yields maximum profit\n",
    "    return indexofElementsInKnapsack"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Problem 1 - Greedy Algorithm \n",
      "Selected w: [ 3  3  5  3  4 12]\n",
      "Selected v: [ 6  8  7 11 13 25]\n",
      "Profit - linear knapsack: 70\n",
      "Weight - linear knapsack: 30\n"
     ]
    }
   ],
   "source": [
    "n = 28\n",
    "v = np.array([2,6,8,7,3,4,6,5,10,9,8,11,12,15,6,8,13,14,15,16,13,14,15,26,13,9,25,26])\n",
    "w = np.array([7,3,3,5,4,7,5,4,15,10,17,3,6,11,6,14,4,8,9,10,14,17,9,24,11,17,12,14])\n",
    "W = 30\n",
    "\n",
    "print(\"Problem 1 - Greedy Algorithm \")    \n",
    "indexofElementsInKnapsack = linearKnapSack(v,w,n,W)\n",
    "print(\"Selected w:\",w[indexofElementsInKnapsack==1])  \n",
    "print(\"Selected v:\",v[indexofElementsInKnapsack==1])  \n",
    "print(\"Profit - linear knapsack:\" , np.sum(v[indexofElementsInKnapsack==1]))\n",
    "print(\"Weight - linear knapsack:\" , np.sum(w[indexofElementsInKnapsack==1]))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 1.2 Polynomial Time Approximation Algorithm"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {},
   "outputs": [],
   "source": [
    "#This function retrieves all subsets in a set recursively.\n",
    "def findSubsets(allSubsets,subset,currentIndex,k):      \n",
    "    if(len(subset) == currentIndex):\n",
    "        return allSubsets\n",
    "    \n",
    "    newSet = []\n",
    "    for i in range(0,len(allSubsets)):\n",
    "      if(len(allSubsets[i]) < k):\n",
    "        newSet = allSubsets[i].copy()\n",
    "        newSet.append(subset[currentIndex])\n",
    "        allSubsets.append(newSet)\n",
    "        \n",
    "    findSubsets(allSubsets, subset, currentIndex+1,k)\n",
    "\n",
    "def isLargerThanCapicity(chosenW,W):\n",
    "      sumWeights = np.sum(chosenW)\n",
    "      if(sumWeights > W):\n",
    "          return True\n",
    "      else:\n",
    "          return False\n",
    "\n",
    "# Find all subsets of a specific size\n",
    "def findAllSubsetsSpecificSize(array, subsetSize,k):\n",
    "    allSubsets = [[]]\n",
    "    findSubsets(allSubsets,array,0,k)\n",
    "    returnSet = []\n",
    "    for sets in allSubsets:\n",
    "        if(len(sets) == subsetSize):\n",
    "            returnSet.append(sets)      \n",
    "    return returnSet\n",
    "\n",
    "#Find all subsets larger than minSubsetSize\n",
    "def findAllSubsetsWithinRange(array, minSubsetSize,k):\n",
    "    allSubsets = [[]]\n",
    "    findSubsets(allSubsets,array,0,k)\n",
    "    returnSet = []\n",
    "    for sets in allSubsets:\n",
    "        if(len(sets) >= minSubsetSize):\n",
    "            returnSet.append(sets)      \n",
    "    return returnSet\n",
    "\n",
    "def PTAS(v,w,n,W,minSizeSubset,k,shouldPrint=False):\n",
    "    currentW = 0\n",
    "    sendW = 0\n",
    "    \n",
    "    allSubsets = [[]]\n",
    "    indexOfSet = []\n",
    "    for i in range(0,28):\n",
    "        indexOfSet.append(i)\n",
    "    \n",
    "    #Step 1 - consider all subsets up to at most k items\n",
    "    allSubsets = findAllSubsetsWithinRange(indexOfSet,minSizeSubset,k)\n",
    "    allSubsetsNumpy = np.array(allSubsets)\n",
    "\n",
    "    highestProfit = 0\n",
    "    bestSetIndex = []\n",
    "    bestLinearIndex = []\n",
    "    \n",
    "    #Step 2  - Pack F into Knapsack\n",
    "    for sets in allSubsetsNumpy:\n",
    "        chosenV = np.take(v,sets)\n",
    "        chosenW = np.take(w,sets)  \n",
    "        if(isLargerThanCapicity(chosenW,W) == False):\n",
    "            otherV = np.take(v,list(set(indexOfSet) - set(sets)))\n",
    "            otherW = np.take(w,list(set(indexOfSet) - set(sets)))\n",
    "            sumProfitPTAS = np.sum(chosenV)\n",
    "            sumWeights = np.sum(chosenW)\n",
    "            remainingW = W - sumWeights\n",
    "            indexofElementsInKnapsack = linearKnapSack(otherV,otherW,len(otherV) ,remainingW)\n",
    "            totalProfit = sumProfitPTAS + np.sum(otherV[indexofElementsInKnapsack==1])\n",
    "            if(shouldPrint):\n",
    "                print(\"Weight - PTAS: \",sumWeights)\n",
    "                print(\"Profit - PTAS: \",sumProfitPTAS)\n",
    "                print(\"Total Profit: \",totalProfit)\n",
    "                print(\"***************************\")\n",
    "                \n",
    "            if(totalProfit >highestProfit ):\n",
    "                highestProfit = totalProfit\n",
    "                bestSetIndex = sets\n",
    "                bestLinearIndex = indexofElementsInKnapsack\n",
    "                bestOtherV = otherV\n",
    "                bestOtherW = otherW\n",
    "    \n",
    "    #Step 2 - Greedily fill the remaining capacity\n",
    "    bestLinearIndexValues = np.where(bestLinearIndex==1)\n",
    "    \n",
    "    print(\"Best Indexs for PTAS:\",bestSetIndex)  \n",
    "    print(\"Selected v - PTAS:\",np.take(v,bestSetIndex))  \n",
    "    print(\"Selected v - Linear:\",np.take(bestOtherV,bestLinearIndexValues)[0]) \n",
    "    \n",
    "    bestValuedV = np.concatenate([np.take(v,bestSetIndex),\n",
    "                np.take(bestOtherV,bestLinearIndexValues)[0]])\n",
    "    bestValuedW = np.concatenate([np.take(w,bestSetIndex),\n",
    "                np.take(bestOtherW,bestLinearIndexValues)[0]])\n",
    "    \n",
    "    #Step 3 - Return Highest valued combination set\n",
    "    return bestValuedV, bestValuedW\n",
    "                                 "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Problem 1 - Polynomial Time Approximation Algorithm (PTAS) \n",
      "Best Indexs for PTAS: [2, 11, 17]\n",
      "Selected v - PTAS: [ 8 11 14]\n",
      "Selected v - Linear: [13 25]\n",
      "Selected v - all: [ 8 11 14 13 25]\n",
      "Selected w - all [ 3  3  8  4 12]\n",
      "Total Weight - all: 30\n",
      "Best Profit - all: 71\n"
     ]
    }
   ],
   "source": [
    "print(\"Problem 1 - Polynomial Time Approximation Algorithm (PTAS) \")\n",
    "minSizeSubset = 3\n",
    "k = 10\n",
    "bestValuedV, bestValuedW = PTAS(v,w,n,W,minSizeSubset,k)\n",
    "\n",
    "print(\"Selected v - all:\",bestValuedV)\n",
    "print(\"Selected w - all\",bestValuedW)\n",
    "print(\"Total Weight - all:\",np.sum(bestValuedW))\n",
    "print(\"Best Profit - all:\",np.sum(bestValuedV))\n",
    "\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<br/> <br/>\n",
    "## Problem 2 - Quadratic Knapsack Problem"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Quadratic Implementation of Knapsack Probelm.\n",
    "Extra profit when choosing certain pairs are considered.\n",
    "<br/> \n",
    "$$ v_i = \\{7, 6, 13, 16, 5, 10, 9, 23, 18, 12, 9, 22, 17, 32, 8\\} $$ <br/>\n",
    "$$ w_i = \\{13, 14, 14, 15, 15, 9, 26, 24, 13, 11, 9, 12, 25, 12, 26\\} , W = 50 $$ <br/>\n",
    "and $$ p_{ij} = \\{(12, 7, 6, 13, 8, 11, 7, 15, 23, 14, 15, 17, 9, 15, 15,\n",
    "13, 10, 15, 9, 10, 8, 17, 11, 13, 12, 16, 15, 11, 16, 6,\n",
    "8, 14, 13, 4, 14, 8, 15, 9, 16, 10, 13, $$<br/>\n",
    "$$ 14, 14, 17, 15, 14, 6, 24, 13, 4, 9, 7, 25, 12, 6,\n",
    "6, 16, 10, 15, 14, 2, 13, 12, 16, 9, 11, 23, 10, 21, 8\n",
    "18, 4, 13, 14, 14, 17, 15, 9, 16, 12, 3, 14, 14, 27, 15, $$ <br/> $$\n",
    "16, 13, 14, 7, 17, 28, 5, 19, 6, 18, 13, 4, 13, 16, 11,19, 13, 15, 12, 16)\\}\n",
    "$$ <br/> <br/>\n",
    "\n",
    "Interpretation of the following steps:\n",
    "- 4 . Add into knapsack the pair of items with the highest score, ensuring that the accumulated\n",
    "weight does not exceed the maximum capacity.\n",
    "- 5 . Repeat steps 1 through 4 until pairs can no longer be added. \n",
    "\n",
    "How they are interpreted:\n",
    "- Once a sample has been selected and pairs have been ordered according to an efficiency function, the pair with the highest efficiency function is selected and it's weight is checked and compared with remaining capacity on the Knapsack, before attempting to add it to the knapsack.\n",
    "-  If the pair with highest efficiency cannot be added to the Knapsack, the data is resampled and the previous step is repeated.\n",
    "- This resampling process happens for 1000 iterations, until attempting to use the linear greedy method."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "metadata": {},
   "outputs": [],
   "source": [
    "import random\n",
    "\n",
    "#Sampling k random items, from a set of Size N - 15 in our case.\n",
    "#alreadySelectedNumbers ensures we do select elements already in the Knsapsack\n",
    "def generateRandomNumbers(k,N,alreadySelectedNumbers ):\n",
    "    #Retrieve unselected numbers/indexs from range(N)\n",
    "    unselectedNumbers = np.delete(range(N),alreadySelectedNumbers)\n",
    "    \n",
    "    #Ensuring that sample size will not be larger than the amount of unselected numbers.\n",
    "    if(len(unselectedNumbers) < k):\n",
    "        numRandomNumbers = len(unselectedNumbers)\n",
    "    else:\n",
    "        numRandomNumbers = k\n",
    "        \n",
    "    #Sampling without replacement - ensuring numbers can't be reselected while sampling.\n",
    "    listRandomIndexs = np.random.choice(unselectedNumbers, numRandomNumbers, replace=False)\n",
    "    return listRandomIndexs\n",
    "    \n",
    "def sortByEfficiencyFunction(arrayOfPairs,p,w):\n",
    "    allEfficiencies = np.array([])\n",
    "    for pair in arrayOfPairs:\n",
    "        P_ij = p[pair[0]][pair[1]]\n",
    "        w_i = w[pair[0]]\n",
    "        w_j = w[pair[1]]\n",
    "        efficiency = P_ij/(w_i+w_j)\n",
    "        allEfficiencies = np.append(allEfficiencies,efficiency)\n",
    "        \n",
    "    efficiencyIndex = np.argsort(-allEfficiencies)\n",
    "    return efficiencyIndex\n",
    "\n",
    "def isAnElementFromPairAlreadySelected(pairToAdd,pairsAlreadyChosen):\n",
    "    indexFirstElementInPair = pairToAdd[0]\n",
    "    indexSecondElementInPair = pairToAdd[1]\n",
    "    \n",
    "    if (indexFirstElementInPair in pairsAlreadyChosen \n",
    "        or indexSecondElementInPair in pairsAlreadyChosen):\n",
    "        return True\n",
    "    else:\n",
    "        return False\n",
    "    \n",
    "def QuadraticKnapsackAlgorithm(k,N,randomSeed,v,w,W,p):\n",
    "    np.random.seed(randomSeed)\n",
    "    indexChosenElements = []\n",
    "    sizeOfArrayOfPairs = 2\n",
    "    sumWeightElementsKnapsack = 0\n",
    "    sumProfit = 0\n",
    "    indexOfSet = []\n",
    "    for i in range(0,15):\n",
    "        indexOfSet.append(i)\n",
    "    \n",
    "    maxIterations = 1000\n",
    "    iterationNumber = 0\n",
    "    #Step 5 - Attempting the Quadratic Knapsack algorithm, while resampling for 1000 iterations\n",
    "    while(iterationNumber< maxIterations):\n",
    "        iterationNumber += 1\n",
    "        # Step 1 - Sampling k items\n",
    "        randomNumberIndex = generateRandomNumbers(k,N,indexChosenElements)\n",
    "        \n",
    "        # Step 2 - Obtaining a set of all pairs\n",
    "        arrayOfPairs = findAllSubsetsSpecificSize(randomNumberIndex,sizeOfArrayOfPairs,k)\n",
    "        \n",
    "        # Step 3-  Sorting according to efficiency function p_ij / (w_i+ w_j) \n",
    "        efficiencyIndexs = sortByEfficiencyFunction(arrayOfPairs,p,w)\n",
    "        scoreIndex = np.argsort(efficiencyIndexs)\n",
    "        \n",
    "        # Adding elements to the Knapsack\n",
    "        currentLargestPair = arrayOfPairs[efficiencyIndexs[0]]\n",
    "        indexFirstElementInPair = currentLargestPair[0]\n",
    "        indexSecondElementInPair = currentLargestPair[1]\n",
    "        w_i = w[indexFirstElementInPair]\n",
    "        w_j = w[indexSecondElementInPair]\n",
    "        \n",
    "        if((sumWeightElementsKnapsack+w_i+w_j) <= W):\n",
    "            if(isAnElementFromPairAlreadySelected(currentLargestPair,indexChosenElements) == False):\n",
    "                indexChosenElements.append(indexFirstElementInPair)\n",
    "                indexChosenElements.append(indexSecondElementInPair)\n",
    "                otherV = np.copy(v)\n",
    "                otherW = np.copy(w)\n",
    "                np.put(otherV,currentLargestPair,0)\n",
    "                sumWeightElementsKnapsack += (w_i+w_j)\n",
    "                sumProfit += (v[indexFirstElementInPair] + v[indexSecondElementInPair])\n",
    "                print(\"Adding Pair - Index (\",currentLargestPair,\"),Value (\",v[indexFirstElementInPair]\n",
    "                      ,v[indexSecondElementInPair],\") Weights(\",w_i,w_j, \") to the knapsack\")  \n",
    "                W = W - sumWeightElementsKnapsack\n",
    "        else:\n",
    "            continue\n",
    "    \n",
    "    selectedVQKP = np.take(v,indexChosenElements)\n",
    "    selectedWQKP = np.take(w,indexChosenElements)\n",
    "    print(\"Weight - QKP:\" , np.sum(selectedWQKP))\n",
    "    print(\"Profit - QKP (Not considering P_ij):\" , np.sum(selectedVQKP))\n",
    "        \n",
    "    #Step 6 - Fill the remaining capacity using the linearGreedyApproach    \n",
    "    indexofElementsInKnapsack = linearKnapSack(otherV,otherW,len(otherV) ,W)\n",
    "    \n",
    "    linearIndex = np.where(indexofElementsInKnapsack == 1)[0]\n",
    "    allIndexs = np.concatenate((linearIndex,indexChosenElements))\n",
    "    \n",
    "    allPairs = findAllSubsetsSpecificSize(allIndexs,sizeOfArrayOfPairs,N)\n",
    "    \n",
    "    singleItemProfit = np.sum(np.concatenate([np.take(v,indexChosenElements),\n",
    "    otherV[indexofElementsInKnapsack==1]]))\n",
    "    totalProfit = singleItemProfit\n",
    "    \n",
    "    for i in range(len(allPairs)):\n",
    "      currentPair = allPairs[i]\n",
    "      totalProfit += p[currentPair[0]][currentPair[1]]\n",
    "    \n",
    "    print(\"Weight - linear knapsack:\" , np.sum(otherW[indexofElementsInKnapsack==1]))\n",
    "    print(\"Profit - linear knapsack:\" , np.sum(otherV[indexofElementsInKnapsack==1]))\n",
    "    \n",
    "    print(\"Selected v - QKP:\",selectedVQKP)  \n",
    "    print(\"Selected v - Linear:\",otherV[indexofElementsInKnapsack==1])  \n",
    "    print(\"Selected w - QKP:\",selectedWQKP)  \n",
    "    print(\"Selected w - Linear:\",otherW[indexofElementsInKnapsack==1]) \n",
    "    \n",
    "    print(\"Selected v - all:\",np.concatenate([np.take(v,indexChosenElements),otherV[indexofElementsInKnapsack==1]]))     \n",
    "    \n",
    "    print(\"Selected w - all: \",np.concatenate([np.take(w,indexChosenElements),\n",
    "    otherW[indexofElementsInKnapsack ==1]]))\n",
    "    print(\"Total Weight - all: \",np.sum(np.concatenate([np.take(w,indexChosenElements),\n",
    "    otherW[indexofElementsInKnapsack ==1]])))\n",
    "    print(\"Total Profit - Single Values:\",singleItemProfit)\n",
    "    print(\"Total Profit - (Including P_ij):\",totalProfit)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Problem 2 - Quadratic Knapsack Problem \n",
      "Adding Pair - Index ( [8, 10] ),Value ( 18 9 ) Weights( 13 9 ) to the knapsack\n",
      "Weight - QKP: 22\n",
      "Profit - QKP (Not considering P_ij): 27\n",
      "Weight - linear knapsack: 24\n",
      "Profit - linear knapsack: 54\n",
      "Selected v - QKP: [18  9]\n",
      "Selected v - Linear: [22 32]\n",
      "Selected w - QKP: [13  9]\n",
      "Selected w - Linear: [12 12]\n",
      "Selected v - all: [18  9 22 32]\n",
      "Selected w - all:  [13  9 12 12]\n",
      "Total Weight - all:  46\n",
      "Total Profit - Single Values: 81\n",
      "Total Profit - (Including P_ij): 162\n"
     ]
    }
   ],
   "source": [
    "print(\"Problem 2 - Quadratic Knapsack Problem \")\n",
    "v = np.array([7, 6, 13,16, 5, 10, 9, 23, 18, 12, 9, 22, 17, 32, 8])\n",
    "w = np.array([13, 14, 14, 15, 15, 9, 26, 24, 13, 11, 9, 12, 25, 12, 26])\n",
    "W = 50\n",
    "p = np.array([\n",
    "7\t,12\t,7\t,6\t,13\t,8\t,11\t,7\t,15\t,23\t,14\t,15\t,17\t,9\t,15,\n",
    "12\t,6\t,15\t,13\t,10\t,15\t,9\t,10\t,8\t,17\t,11\t,13\t,12\t,16\t,15,\n",
    "7\t,15\t,13\t,11\t,16\t,6\t,8\t,14\t,13\t,4\t,14\t,8\t,15\t,9\t,16,\n",
    "6\t,13\t,11\t,16\t,10\t,13\t,14\t,14\t,17\t,15\t,14\t,6\t,24\t,13\t, 4,\n",
    "13\t,10\t,16\t,10\t,5\t,9\t,7\t,25\t,12\t,6\t,6\t,16\t,10\t,15\t,14,\n",
    "8\t,15\t,6\t,13\t,9\t,10\t,2\t,13\t,12\t,16\t,9\t,11\t,23\t,10\t,21,\n",
    "11\t,9\t,8\t,14\t,7\t,2\t,9\t,8\t,18\t,4\t,13\t,14\t,14\t,17\t,15,\n",
    "7\t,10\t,14\t,14\t,25\t,13\t,8\t,23\t,9\t,16\t,12\t,3\t,14\t,14\t,27,\n",
    "15\t,8\t,13\t,17\t,12\t,12\t,18\t,9\t,18\t,15\t,16\t,13\t,14\t,7\t,17,\n",
    "23\t,17\t,4\t,15\t,6\t,16\t,4\t,16\t,15\t,12\t,28\t,5\t,19\t,6\t,18,\n",
    "14\t,11\t,14\t,14\t,6\t,9\t,13\t,12\t,16\t,28\t,9\t,13\t,4\t,13\t,16,\n",
    "15\t,13\t,8\t,6\t,16\t,11\t,14\t,3\t,13\t,5\t,13\t,22\t,11\t,19\t,13,\n",
    "17\t,12\t,15\t,24\t,10\t,23\t,14\t,14\t,14\t,19\t,4\t,11\t,17\t,15\t,12,\n",
    "9\t,16\t,9\t,13\t,15\t,10\t,17\t,14\t,7\t,6\t,13\t,19\t,15\t,32\t,16,\n",
    "15\t,15\t,16\t,4\t,14\t,21\t,15\t,27\t,17\t,18\t,16\t,13\t,12\t,16\t, 8\n",
    "    ])\n",
    "p = p.reshape(15,15)\n",
    "k = 7\n",
    "N = 15\n",
    "randomSeed = 7\n",
    "\n",
    "QuadraticKnapsackAlgorithm(k,N,randomSeed,v,w,W,p)"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.6.4"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}