Skip to content
  • Home
  • Contact Us
  • About Us
  • Privacy Policy
  • DMCA
  • Linkedin
  • Pinterest
  • Facebook
thecscience

TheCScience

TheCScience is a blog that publishes daily tutorials and guides on engineering subjects and everything that related to computer science and technology

  • Home
  • Human values
  • Microprocessor
  • Digital communication
  • Linux
  • outsystems guide
  • Toggle search form
HackerRank Knapsack Problem Solution

HackerRank Knapsack Problem Solution

Posted on July 18, 2023July 18, 2023 By Yashwant Parihar No Comments on 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

2
3 12
1 6 9
5 9
3 4 4 4 8

Sample Output

12
9

Explanation

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

HackerRank Knapsack Problem Solution
HackerRank Knapsack Problem Solution

Table of Contents

  • Knapsack C Solution
  • Knapsack C++ Solution
  • Knapsack C Sharp Solution
  • Knapsack Java Solution
  • Knapsack JavaScript Solution
  • Knapsack Python Solution

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()
c, C#, C++, HackerRank Solutions, java, javascript, python Tags:C, cpp, CSharp, Hackerrank Solutions, java, javascript, python

Post navigation

Previous Post: HackerRank Matrix Land Problem Solution
Next Post: HackerRank Bricks Game Problem Solution

Related Posts

HackerRank Longest Mod Path Problem Solution HackerRank Longest Mod Path Problem Solution c
HackerRank Airports Problem Solution HackerRank Airports Problem Solution c
HackerRank Similar Strings Problem Solution HackerRank Similar Strings Problem Solution c
HackerRank Fair Rations Problem Solution HackerRank Fair Rations Problem Solution c
HackerRank Mr K marsh Problem Solution HackerRank Mr K marsh Problem Solution c
HackerRank Chocolate Feast Problem Solution HackerRank Chocolate Feast Problem Solution c

Leave a Reply Cancel reply

Your email address will not be published. Required fields are marked *

Pick Your Subject
Human Values

Copyright © 2023 TheCScience.

Powered by PressBook Grid Blogs theme