HackerRank Knapsack Problem Solution

In this post, we will solve HackerRank Knapsack Problem Solution.

You are playing a matrix-based game with the following setup and rules:

You are given a matrix A with n rows and m columns. Each cell contains some points. When a player passes a cell their score increases by the number written in that cell and the number in the cell becomes 0. (If the cell number is positive their score increases, otherwise it decreases.)
The player starts from any cell in the first row and can move left, right or down.
The game is over when the player reaches the last row and stops moving.

Output Format

Print the maximum sum for each test case which is as near as possible, but not exceeding, to the target sum on a separate line.

Sample Input

Sample Output

12
9

Explanation

In the first test case, one can pick {6, 6}. In the second, we can pick {3,3,3}.

Table of Contents

Knapsack C Solution

#include <stdio.h>

#define NMAX 2005
#define MAX(a, b, c) (a >= b && a >= c) ? a : ((b >= a && b >= c) ? b : c)

int dp[NMAX][NMAX];
int A[NMAX];

int main()
{
    int T, N, K, i, j;
    
    scanf("%d", &T);
    while(T--){
        scanf("%d %d", &N, &K);
        for(i = 1; i <= N; i++)
            scanf("%d", &A[i]);
            
        for(i = 0; i <= N; i++){
            for(j = 0; j <= K; j++){
                if(i == 0 || j == 0)
                    dp[i][j] = 0;
                else if(A[i] > j)
                    dp[i][j] = dp[i - 1][j];
                else
                    dp[i][j] = MAX(dp[i - 1][j - A[i]] + A[i], dp[i][j - A[i]] + A[i], dp[i - 1][j]);
            }
        }
        
        printf("%d\n", dp[N][K]);
    }

    return 0;
}

Knapsack C++ Solution

#include <cmath>
#include <cstdio>
#include <cstring>
#include <vector>
#include <iostream>
#include <algorithm>
using namespace std;

int dp[2005][2005];

int solve(const vector<int> &v, const int &K, int at, int cur) {
    if (cur > K) return 0;
    if (at == v.size()) return cur;
    int &ans = dp[at][cur];
    if (ans != -1) return ans;
    ans = 0;
    ans = max(solve(v, K, at, cur+v[at]), solve(v, K, at+1, cur));
    return ans;
}

void solve() {
    int N, K;
    cin >> N >> K;
    vector<int> numbers;
    for (int i = 0; i < N; ++i) {
        int cur;
        cin >> cur;
        numbers.push_back(cur);
    }
    memset(dp, -1, sizeof(dp));
    cout << solve(numbers, K, 0, 0) << endl;
}

int main() {
    int T;
    cin >> T;
    for (int i = 0; i < T; ++i) solve();
    /* Enter your code here. Read input from STDIN. Print output to STDOUT */   
    return 0;
}

Knapsack C Sharp Solution

using System;
using System.Collections.Generic;
using System.IO;
class Solution {
    public static void Main(string[] args) {
		string testCaseConfig = Console.ReadLine();
		int testCases = int.Parse(testCaseConfig);
		for(int testCase = 0; testCase < testCases; testCase++) {
			var problem = KSProblem.ParseFromInput();
			var result = problem.Solve();
			Console.WriteLine(result);
		}
	}
	
	private class KSProblem {
		
		public int Target { get; set; }
		public List<int> Items { get; set; }
		public Dictionary<int, int> calculated = new Dictionary<int, int>();
		
		public static KSProblem ParseFromInput(){
			KSProblem problem = new KSProblem();
			
			string config = Console.ReadLine();
			string[] configParts = config.Split(' ');
			int itemCount = int.Parse(configParts[0]);
			problem.Target = int.Parse(configParts[1]);
			problem.Items = new List<int>();
			string[] itemConfig = Console.ReadLine().Split(' ');
			for(int itemIndex = 0; itemIndex < itemCount; itemIndex++) {
				int item = int.Parse(itemConfig[itemIndex]);
				problem.Items.Add(item);
			}
			return problem;
		}
	
		public int Solve() {
			return Math.Max(this.Target - SolveFor(this.Target), 0);
		}
		
		private int SolveFor(int target) {
			if(calculated.ContainsKey(target)){
				return calculated[target];
			}
		
			var remaining = target;
			if(target < 0) {
				return int.MaxValue;
			}
			foreach(int item in this.Items){
				remaining = Math.Min(remaining, SolveFor(target - item));
			}
			calculated[target] = remaining;
			return remaining;
		}
	}
}

Knapsack Java Solution

import java.util.Arrays;
import java.util.HashSet;
import java.util.Iterator;
import java.util.Scanner;

public class Solution {

    private static Scanner sc;

    /**
     * @param args
     */
    public static void main(String[] args) {
        sc = new Scanner(System.in);
        int T = sc.nextInt();
        for (int i = 0; i < T; i++) {
            int n = sc.nextInt();
            int k = sc.nextInt();
            HashSet<Integer> map = new HashSet<Integer>();
            for (int j = 0; j < n; j++) {
                map.add(sc.nextInt());
            }
            System.out.println(getMultSum(map, k));
        }
    }

    private static int getMultSum(HashSet<Integer> map, int k) {
        Iterator<Integer> it = map.iterator();
        boolean[] sum = new boolean[k + 1];
        Arrays.fill(sum, false);
        sum[0] = true;
        int a = 0;
        for (int i = 0; i <= k; i++) {

            if (sum[i] == true) {
                it = map.iterator();
                while (it.hasNext()) {
                    a = it.next();
                    if ((i + a) <= k)
                        sum[i + a] = true;
                }
            }
        }
        for(int i=k;i>=0;i--){
            if(sum[i] == true){
                return i;
            }
        }
        return 0;
    }
}

Knapsack JavaScript Solution

Array.matrix = function(numrows, numcols, initial){
   var arr = [];
   for (var i = 0; i < numrows; ++i){
      var columns = [];
      for (var j = 0; j < numcols; ++j){
         columns[j] = initial;
      }
      arr[i] = columns;
    }
    return arr;
}

function knapsack(A, k) {
    
    k = parseInt(k);
    
    var solution = Array.matrix(A.length + 1, k+1, 0);
    
    for(var i = 0; i<= A.length; i++) {
        solution[i][0] = 0
    }

    for(var j = 0; j<= k; j++) {
        solution[0][j] = 0
    }
    
    for(var i = 1; i<= A.length; i++) {
        for(j=1; j <= k; j++) {
            solution[i][j] = solution[i-1][j];
            if(A[i-1] <= j) {
                solution[i][j] = Math.max(A[i-1] + solution[i][j - A[i-1]], A[i-1] + solution[i-1][j - A[i-1]], solution[i-1][j]);
            }
            /*
            if(A[i-1] <= j) {
                solution[i][j] = Math.max(A[i-1] + solution[i][j - A[i-1]], A[i-1] + solution[i-1][j - A[i-1]], solution[i-1][j]);
            }
            else {
                solution[i][j] = solution[i-1][j];
            }
            */
        }
    }
   
    //console.log(solution);
    console.log(solution[A.length][k]);
}


function processData(input) {
    //Enter your code here
    var lines = input.split("\n");
    
    /*
    var T = lines[0];
    if(parseInt(T) > 10) {
        console.log(0);
        return;
    }
    */
    var testCase = {};
    var line = "";
    var A = [];
    var k = 0;
    for(var i = 1; i<lines.length; i = i+2) {
        line = lines[i];
        
        k = line.split(" ")[1];
        A = lines[i+1].split(" ");

        A = A.map(Number);
        A = A.filter(function(elem, pos,arr) {
            return arr.indexOf(elem) == pos;
         }); 
        
        knapsack(A, k);
    }
    
} 

process.stdin.resume();
process.stdin.setEncoding("ascii");
_input = "";
process.stdin.on("data", function (input) {
    _input += input;
});

process.stdin.on("end", function () {
   processData(_input);
});

Knapsack Python Solution

# https://www.hackerrank.com/challenges/unbounded-knapsack

def readInput():
    in_array = []
    no_of_test_cases = int(input())
    for i in range(no_of_test_cases):
        target = int(input().split()[1])  # get expected sum
        in_array.append((target, set(map(lambda x: int(x), input().split()))))
    return in_array

def solve(test_case):
    expectedSum = test_case[0]
    values = test_case[1]
    solution = [0]
    for i in range(expectedSum+1):
        if i in values:
            solution.append(i)
        else:
            for j in range(len(solution) - 1, -1, -1):
                if i - solution[j] in values:
                    solution.append(i)
                    break
    return max(solution)

def run():
    test_cases = readInput()
    for testCase in test_cases:
        print(solve(testCase))

run()