Так что, если вы не знаете, в чем проблема рюкзака, это способ подбора различных весов из рюкзака, чтобы они в сумме равнялись указанному общему весу.Вот пример из моей книги о том, как решить проблему, если указанный общий вес был 20.
Если кто-нибудь знает, как реализовать эту проблему в Java с помощью рекурсииПОЖАЛУЙСТА, помогите, я так растерялся.Вот что я начал, но я уверен, что это неправильно, и я понятия не имею, куда идти.
import java.util.*;
public class n01044854 {
public static void main(String[] args) {
Scanner input = new Scanner(System.in);
System.out.println("Please first enter a weight capacity up to a value of
100, followed by a series of individual weight values with 25 weights being the max.)
");
String values = input.nextLine();
String[] tokens = values.split(" +");
int capacity = Integer.parseInt(tokens[0]);
int[] weightValues = new int[tokens.length - 1];
for (int i = 0; i < tokens.length - 1; i++)
weightValues[i] = Integer.parseInt(tokens[i+1]);
optimizeWeights(capacity, weightValues, 0);
}
public static void optimizeWeights(int target, int[] weights, int currentIndex) {
if (weights[currentIndex] == target)
System.out.println("Success! Knapsack optimally filled.");
else if (weights[currentIndex] < target) {
int newTarget = target - weights[currentIndex];
optimizeWeights(newTarget, weights, currentIndex + 1);
} else if (weights[currentIndex] > target) {
if (currentIndex < weights.length - 1)
optimizeWeights(target, weights, currentIndex + 1);
else
//confused on what to do
}
}
}