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}.
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()
