Computer scienceProgramming languagesJavaInterview preparationAlgorithms and problem solving techniques

Dynamic programming approach in action

Knapsack

Report a typo

Imagine that there is a knapsack with a certain capacity and a number of items with a certain weight and value. Items are represented by the Item class that has two getters, getWeight() and getValue() that return the item's weight and value respectively. Write a method that accepts an array of Item objects and a knapsack's capacity and finds the maximum possible total value of the items you can put in the knapsack.

Check this picture:

the scheme of the items in the knapsack

The knapsack has the capacity of 5 and there are four available items. We can get the maximum possible value of 7 if we put these two items in the knapsack. Remember that we can put each item only once!

Sample Input 1:

capacity=5
weight=4, value=5
weight=2, value=3
weight=3, value=2
weight=1, value=2

Sample Output 1:

Sample Input 2:

capacity=6
weight=6, value=9
weight=1, value=5
weight=5, value=4
weight=5, value=16
weight=8, value=16
weight=1, value=5
weight=4, value=8
weight=6, value=9
weight=8, value=3
weight=5, value=13

Sample Output 2:

Sample Input 3:

capacity=11
weight=6, value=6
weight=6, value=17
weight=8, value=5
weight=6, value=8
weight=3, value=15

Sample Output 3:

Write a program in Java 17

import java.util.Scanner;

class Main {

// Implement this method, write a helper method if necessary

private static int findMaxValue(Item[] items, int capacity) {

return 0;

}

// Do not modify the code below

public static void main(String[] args) {

Scanner scanner = new Scanner(System.in);

var tokens = scanner.useDelimiter("\\R").tokens().toList();

int capacity = Integer.parseInt(tokens.get(0).split("=")[1]);

Item[] items = tokens.stream()

.skip(1)

.filter(s -> !s.isEmpty())

.map(s -> s.split(", "))

.map(arr -> {

int weight = Integer.parseInt(arr[0].split("=")[1]);

int value = Integer.parseInt(arr[1].split("=")[1]);

return new Item(weight, value);

})

.toArray(Item[]::new);

int result = findMaxValue(items, capacity);

System.out.println(result);

}

class Item {

private final int weight;

private final int value;

public Item(int weight, int value) {

this.weight = weight;

this.value = value;

___

Create a free account to access the full topic