Как мне рекурсивно решить "классический" алгоритм ранца?
Это моя задача
Задача о ранце - это классика информатики. В своей простейшей форме это включает в себя попытку поместить предметы разного веса в рюкзак, чтобы у рюкзака был общий вес. Вам не нужно вписываться во все предметы. Например, предположим, что вы хотите, чтобы ваш рюкзак весил ровно 20 фунтов, и у вас есть пять предметов весом 11, 8, 7, 6 и 5 фунтов. Для небольшого количества предметов люди довольно хорошо решают эту проблему путем проверки. Таким образом, вы, вероятно, можете понять, что только 8, 7 и 5 комбинаций предметов складываются до 20.
Я действительно не знаю, с чего начать писать этот алгоритм. Я понимаю рекурсию применительно к факториалам и числам треугольников. Однако я потерялся прямо сейчас.
10 ответов
Что ты пробовал?
Идея, учитывая указанную вами проблему (которая указывает на то, что мы должны использовать рекурсию), проста: для каждого предмета, который вы можете взять, посмотрите, лучше его взять или нет. Таким образом, есть только два возможных пути:
- вы берете предмет
- ты не принимаешь это
Когда вы берете предмет, вы удаляете его из списка и уменьшаете емкость на вес предмета.
Если вы не берете предмет, вы удаляете его из списка, но не уменьшаете емкость.
Иногда это помогает напечатать, как могут выглядеть рекурсивные вызовы. В этом случае это может выглядеть так:
Calling 11 8 7 6 5 with cap: 20
+Calling 8 7 6 5 with cap: 20
| Calling 7 6 5 with cap: 20
| Calling 6 5 with cap: 20
| Calling 5 with cap: 20
| Result: 5
| Calling 5 with cap: 14
| Result: 5
| Result: 11
| Calling 6 5 with cap: 13
| Calling 5 with cap: 13
| Result: 5
| Calling 5 with cap: 7
| Result: 5
| Result: 11
| Result: 18
| Calling 7 6 5 with cap: 12
| Calling 6 5 with cap: 12
| Calling 5 with cap: 12
| Result: 5
| Calling 5 with cap: 6
| Result: 5
| Result: 11
| Calling 6 5 with cap: 5
| Calling 5 with cap: 5
| Result: 5
| Result: 5
| Result: 12
+Result: 20
Calling 8 7 6 5 with cap: 9
Calling 7 6 5 with cap: 9
Calling 6 5 with cap: 9
Calling 5 with cap: 9
Result: 5
Calling 5 with cap: 3
Result: 0
Result: 6
Calling 6 5 with cap: 2
Calling 5 with cap: 2
Result: 0
Result: 0
Result: 7
Calling 7 6 5 with cap: 1
Calling 6 5 with cap: 1
Calling 5 with cap: 1
Result: 0
Result: 0
Result: 0
Result: 8
Result: 20
Я специально показывал вызов [8 7 6 5] емкостью 20, что дает результат 20 (8 + 7 + 5).
Обратите внимание, что [8 7 6 5] вызывается дважды: один раз с емкостью 20 (потому что мы не взяли 11) и один раз с емкостью 9 (потому что с действительно взял 11).
Итак, путь к решению:
11 не принято, вызывая [8 7 6 5] с вместимостью 20
8 принято, вызывая [7 6 5] вместимостью 12 (20 - 8)
7 принято, вызывая [6 5] вместимостью 5 (12 - 7)
6 не принято, вызов [5] с вместимостью 5
5 принято, мы на нуле.
Фактический метод в Java может вместить очень мало строк кода.
Поскольку это, очевидно, домашнее задание, я просто помогу вам со скелетом:
private int ukp( final int[] ar, final int cap ) {
if ( ar.length == 1 ) {
return ar[0] <= cap ? ar[0] : 0;
} else {
final int[] nar = new int[ar.length-1];
System.arraycopy(ar, 1, nar, 0, nar.length);
fint int item = ar[0];
if ( item < cap ) {
final int left = ... // fill me: we're not taking the item
final int took = ... // fill me: we're taking the item
return Math.max(took,left);
} else {
return ... // fill me: we're not taking the item
}
}
}
Я скопировал массив в новый массив, который менее эффективен (но в любом случае рекурсия - это не тот путь, если вы ищете производительность), но более "функциональный".
Я должен был сделать это для своей домашней работы, поэтому я протестировал все вышеперечисленные коды (кроме Python), но ни один из них не работал для каждого углового случая.
Это мой код, он работает для каждого углового случая.
static int[] values = new int[] {894, 260, 392, 281, 27};
static int[] weights = new int[] {8, 6, 4, 0, 21};
static int W = 30;
private static int knapsack(int i, int W) {
if (i < 0) {
return 0;
}
if (weights[i] > W) {
return knapsack(i-1, W);
} else {
return Math.max(knapsack(i-1, W), knapsack(i-1, W - weights[i]) + values[i]);
}
}
public static void main(String[] args) {
System.out.println(knapsack(values.length - 1, W));}
Он не оптимизирован, рекурсия убьет вас, но вы можете использовать простое напоминание, чтобы это исправить. Почему мой код короткий, правильный и простой для понимания? Я только что проверил математическое определение проблемы ранца 0-1 http://en.wikipedia.org/wiki/Knapsack_problem
Проблема в основном является модифицированной версией классической задачи о ранце для простоты (нет значений / преимуществ, соответствующих весам) (для фактических данных: http://en.wikipedia.org/wiki/Knapsack_problem, 0/1 ранца - несколько пояснений по Псевдокод Wiki, Как понять, что проблема рюкзака является NP-полной?, Почему проблема рюкзака псевдополином??, http://www.geeksforgeeks.org/dynamic-programming-set-10-0-1-knapsack-problem/).
Вот пять версий решения этой проблемы в C#:
версия 1: Использование динамического программирования (в виде таблицы - с нетерпением жду решения всех проблем сумм, чтобы добраться до финальной) - O(n * W)
версия 2: Использование DP, но версия для запоминания (ленивый - просто поиск решений для всего, что нужно)
версия 3 Использование рекурсии для демонстрации перекрывающихся подзадач и оптимальной подструктуры
Версия 4 Рекурсивная (грубая сила) - в основном принятый ответ
версия 5 Использование стека #4 (демонстрация удаления хвостовой рекурсии)
версия 1: Использование динамического программирования (в виде таблицы - с нетерпением жду решения всех проблем сумм, чтобы добраться до финальной) - O(n * W)
public bool KnapsackSimplified_DP_Tabulated_Eager(int[] weights, int W)
{
this.Validate(weights, W);
bool[][] DP_Memoization_Cache = new bool[weights.Length + 1][];
for (int i = 0; i <= weights.Length; i++)
{
DP_Memoization_Cache[i] = new bool[W + 1];
}
for (int i = 1; i <= weights.Length; i++)
{
for (int w = 0; w <= W; w++)
{
/// f(i, w) determines if weight 'w' can be accumulated using given 'i' number of weights
/// f(i, w) = False if i <= 0
/// OR True if weights[i-1] == w
/// OR f(i-1, w) if weights[i-1] > w
/// OR f(i-1, w) || f(i-1, w-weights[i-1])
if(weights[i-1] == w)
{
DP_Memoization_Cache[i][w] = true;
}
else
{
DP_Memoization_Cache[i][w] = DP_Memoization_Cache[i - 1][w];
if(!DP_Memoization_Cache[i][w])
{
if (w > weights[i - 1])
{
DP_Memoization_Cache[i][w] = DP_Memoization_Cache[i - 1][w - weights[i - 1]];
}
}
}
}
}
return DP_Memoization_Cache[weights.Length][W];
}
версия 2: Использование DP, но версия для запоминания (ленивый - просто поиск решений для всего, что нужно)
/// <summary>
/// f(i, w) determines if weight 'w' can be accumulated using given 'i' number of weights
/// f(i, w) = False if i < 0
/// OR True if weights[i] == w
/// OR f(i-1, w) if weights[i] > w
/// OR f(i-1, w) || f(i-1, w-weights[i])
/// </summary>
/// <param name="rowIndexOfCache">
/// Note, its index of row in the cache
/// index of given weifhts is indexOfCahce -1 (as it starts from 0)
/// </param>
bool KnapsackSimplified_DP_Memoization_Lazy(int[] weights, int w, int i_rowIndexOfCache, bool?[][] DP_Memoization_Cache)
{
if(i_rowIndexOfCache < 0)
{
return false;
}
if(DP_Memoization_Cache[i_rowIndexOfCache][w].HasValue)
{
return DP_Memoization_Cache[i_rowIndexOfCache][w].Value;
}
int i_weights_index = i_rowIndexOfCache - 1;
if (weights[i_weights_index] == w)
{
//we can just use current weight, so no need to call other recursive methods
//just return true
DP_Memoization_Cache[i_rowIndexOfCache][w] = true;
return true;
}
//see if W, can be achieved without using weights[i]
bool flag = this.KnapsackSimplified_OverlappedSubPromblems_OptimalSubstructure(weights,
w, i_rowIndexOfCache - 1);
DP_Memoization_Cache[i_rowIndexOfCache][w] = flag;
if (flag)
{
return true;
}
if (w > weights[i_weights_index])
{
//see if W-weight[i] can be achieved with rest of the weights
flag = this.KnapsackSimplified_OverlappedSubPromblems_OptimalSubstructure(weights,
w - weights[i_weights_index], i_rowIndexOfCache - 1);
DP_Memoization_Cache[i_rowIndexOfCache][w] = flag;
}
return flag;
}
где
public bool KnapsackSimplified_DP_Memoization_Lazy(int[] weights, int W)
{
this.Validate(weights, W);
//note 'row' index represents the number of weights been used
//note 'colum' index represents the weight that can be achived using given
//number of weights 'row'
bool?[][] DP_Memoization_Cache = new bool?[weights.Length+1][];
for(int i = 0; i<=weights.Length; i++)
{
DP_Memoization_Cache[i] = new bool?[W + 1];
for(int w=0; w<=W; w++)
{
if(i != 0)
{
DP_Memoization_Cache[i][w] = null;
}
else
{
//can't get to weight 'w' using none of the given weights
DP_Memoization_Cache[0][w] = false;
}
}
DP_Memoization_Cache[i][0] = false;
}
bool f = this.KnapsackSimplified_DP_Memoization_Lazy(
weights, w: W, i_rowIndexOfCache: weights.Length, DP_Memoization_Cache: DP_Memoization_Cache);
Assert.IsTrue(f == DP_Memoization_Cache[weights.Length][W]);
return f;
}
версия 3 Идентификация перекрывающихся подзадач и оптимальной подструктуры
/// <summary>
/// f(i, w) = False if i < 0
/// OR True if weights[i] == w
/// OR f(i-1, w) if weights[i] > w
/// OR f(i-1, w) || f(i-1, w-weights[i])
/// </summary>
public bool KnapsackSimplified_OverlappedSubPromblems_OptimalSubstructure(int[] weights, int W, int i)
{
if(i<0)
{
//no more weights to traverse
return false;
}
if(weights[i] == W)
{
//we can just use current weight, so no need to call other recursive methods
//just return true
return true;
}
//see if W, can be achieved without using weights[i]
bool flag = this.KnapsackSimplified_OverlappedSubPromblems_OptimalSubstructure(weights,
W, i - 1);
if(flag)
{
return true;
}
if(W > weights[i])
{
//see if W-weight[i] can be achieved with rest of the weights
return this.KnapsackSimplified_OverlappedSubPromblems_OptimalSubstructure(weights, W - weights[i], i - 1);
}
return false;
}
где
public bool KnapsackSimplified_OverlappedSubPromblems_OptimalSubstructure(int[] weights, int W)
{
this.Validate(weights, W);
bool f = this.KnapsackSimplified_OverlappedSubPromblems_OptimalSubstructure(weights, W,
i: weights.Length - 1);
return f;
}
версия 4 Грубая сила
private bool KnapsackSimplifiedProblemRecursive(int[] weights, int sum, int currentSum, int index, List<int> itemsInTheKnapsack)
{
if (currentSum == sum)
{
return true;
}
if (currentSum > sum)
{
return false;
}
if (index >= weights.Length)
{
return false;
}
itemsInTheKnapsack.Add(weights[index]);
bool flag = KnapsackSimplifiedProblemRecursive(weights, sum, currentSum: currentSum + weights[index],
index: index + 1, itemsInTheKnapsack: itemsInTheKnapsack);
if (!flag)
{
itemsInTheKnapsack.Remove(weights[index]);
flag = KnapsackSimplifiedProblemRecursive(weights, sum, currentSum, index + 1, itemsInTheKnapsack);
}
return flag;
}
public bool KnapsackRecursive(int[] weights, int sum, out List<int> knapsack)
{
if(sum <= 0)
{
throw new ArgumentException("sum should be +ve non zero integer");
}
knapsack = new List<int>();
bool fits = KnapsackSimplifiedProblemRecursive(weights, sum, currentSum: 0, index: 0,
itemsInTheKnapsack: knapsack);
return fits;
}
версия 5: итеративная версия с использованием стека (примечание - та же сложность - использование стека - удаление хвостовой рекурсии)
public bool KnapsackIterativeUsingStack(int[] weights, int sum, out List<int> knapsack)
{
sum.Throw("sum", s => s <= 0);
weights.ThrowIfNull("weights");
weights.Throw("weights", w => (w.Length == 0)
|| w.Any(wi => wi < 0));
var knapsackIndices = new List<int>();
knapsack = new List<int>();
Stack<KnapsackStackNode> stack = new Stack<KnapsackStackNode>();
stack.Push(new KnapsackStackNode() { sumOfWeightsInTheKnapsack = 0, nextItemIndex = 1 });
stack.Push(new KnapsackStackNode() { sumOfWeightsInTheKnapsack = weights[0], nextItemIndex = 1, includesItemAtCurrentIndex = true });
knapsackIndices.Add(0);
while(stack.Count > 0)
{
var top = stack.Peek();
if(top.sumOfWeightsInTheKnapsack == sum)
{
int count = 0;
foreach(var index in knapsackIndices)
{
var w = weights[index];
knapsack.Add(w);
count += w;
}
Debug.Assert(count == sum);
return true;
}
//basically either of the below three cases, we dont need to traverse/explore adjuscent
// nodes further
if((top.nextItemIndex == weights.Length) //we reached end, no need to traverse
|| (top.sumOfWeightsInTheKnapsack > sum) // last added node should not be there
|| (top.alreadyExploredAdjuscentItems)) //already visted
{
if (top.includesItemAtCurrentIndex)
{
Debug.Assert(knapsackIndices.Contains(top.nextItemIndex - 1));
knapsackIndices.Remove(top.nextItemIndex - 1);
}
stack.Pop();
continue;
}
var node1 = new KnapsackStackNode();
node1.sumOfWeightsInTheKnapsack = top.sumOfWeightsInTheKnapsack;
node1.nextItemIndex = top.nextItemIndex + 1;
stack.Push(node1);
var node2 = new KnapsackStackNode();
knapsackIndices.Add(top.nextItemIndex);
node2.sumOfWeightsInTheKnapsack = top.sumOfWeightsInTheKnapsack + weights[top.nextItemIndex];
node2.nextItemIndex = top.nextItemIndex + 1;
node2.includesItemAtCurrentIndex = true;
stack.Push(node2);
top.alreadyExploredAdjuscentItems = true;
}
return false;
}
где
class KnapsackStackNode
{
public int sumOfWeightsInTheKnapsack;
public int nextItemIndex;
public bool alreadyExploredAdjuscentItems;
public bool includesItemAtCurrentIndex;
}
И юнит-тесты
[TestMethod]
public void KnapsackSimpliedProblemTests()
{
int[] weights = new int[] { 7, 5, 4, 4, 1 };
List<int> bag = null;
bool flag = this.KnapsackSimplifiedProblemIterativeUsingStack(weights, 10, knapsack: out bag);
Assert.IsTrue(flag);
Assert.IsTrue(bag.Contains(5));
Assert.IsTrue(bag.Contains(4));
Assert.IsTrue(bag.Contains(1));
Assert.IsTrue(bag.Count == 3);
flag = this.KnapsackSimplifiedProblemIterativeUsingStack(weights, 3, knapsack: out bag);
Assert.IsFalse(flag);
flag = this.KnapsackSimplifiedProblemIterativeUsingStack(weights, 7, knapsack: out bag);
Assert.IsTrue(flag);
Assert.IsTrue(bag.Contains(7));
Assert.IsTrue(bag.Count == 1);
flag = this.KnapsackSimplifiedProblemIterativeUsingStack(weights, 1, knapsack: out bag);
Assert.IsTrue(flag);
Assert.IsTrue(bag.Contains(1));
Assert.IsTrue(bag.Count == 1);
flag = this.KnapsackSimplified_DP_Tabulated_Eager(weights, 10);
Assert.IsTrue(flag);
flag = this.KnapsackSimplified_DP_Tabulated_Eager(weights, 3);
Assert.IsFalse(flag);
flag = this.KnapsackSimplified_DP_Tabulated_Eager(weights, 7);
Assert.IsTrue(flag);
flag = this.KnapsackSimplified_DP_Tabulated_Eager(weights, 1);
Assert.IsTrue(flag);
flag = this.KnapsackSimplified_DP_Memoization_Lazy(weights, 10);
Assert.IsTrue(flag);
flag = this.KnapsackSimplified_DP_Memoization_Lazy(weights, 3);
Assert.IsFalse(flag);
flag = this.KnapsackSimplified_DP_Memoization_Lazy(weights, 7);
Assert.IsTrue(flag);
flag = this.KnapsackSimplified_DP_Memoization_Lazy(weights, 1);
Assert.IsTrue(flag);
flag = this.KnapsackSimplified_OverlappedSubPromblems_OptimalSubstructure(weights, 10);
Assert.IsTrue(flag);
flag = this.KnapsackSimplified_OverlappedSubPromblems_OptimalSubstructure(weights, 3);
Assert.IsFalse(flag);
flag = this.KnapsackSimplified_OverlappedSubPromblems_OptimalSubstructure(weights, 7);
Assert.IsTrue(flag);
flag = this.KnapsackSimplified_OverlappedSubPromblems_OptimalSubstructure(weights, 1);
Assert.IsTrue(flag);
flag = this.KnapsackRecursive(weights, 10, knapsack: out bag);
Assert.IsTrue(flag);
Assert.IsTrue(bag.Contains(5));
Assert.IsTrue(bag.Contains(4));
Assert.IsTrue(bag.Contains(1));
Assert.IsTrue(bag.Count == 3);
flag = this.KnapsackRecursive(weights, 3, knapsack: out bag);
Assert.IsFalse(flag);
flag = this.KnapsackRecursive(weights, 7, knapsack: out bag);
Assert.IsTrue(flag);
Assert.IsTrue(bag.Contains(7));
Assert.IsTrue(bag.Count == 1);
flag = this.KnapsackRecursive(weights, 1, knapsack: out bag);
Assert.IsTrue(flag);
Assert.IsTrue(bag.Contains(1));
Assert.IsTrue(bag.Count == 1);
weights = new int[] { 11, 8, 7, 6, 5 };
flag = this.KnapsackSimplifiedProblemIterativeUsingStack(weights, 20, knapsack: out bag);
Assert.IsTrue(bag.Contains(8));
Assert.IsTrue(bag.Contains(7));
Assert.IsTrue(bag.Contains(5));
Assert.IsTrue(bag.Count == 3);
flag = this.KnapsackSimplifiedProblemIterativeUsingStack(weights, 27, knapsack: out bag);
Assert.IsFalse(flag);
flag = this.KnapsackSimplifiedProblemIterativeUsingStack(weights, 11, knapsack: out bag);
Assert.IsTrue(flag);
Assert.IsTrue(bag.Contains(11));
Assert.IsTrue(bag.Count == 1);
flag = this.KnapsackSimplifiedProblemIterativeUsingStack(weights, 5, knapsack: out bag);
Assert.IsTrue(flag);
Assert.IsTrue(bag.Contains(5));
Assert.IsTrue(bag.Count == 1);
flag = this.KnapsackRecursive(weights, 20, knapsack: out bag);
Assert.IsTrue(bag.Contains(8));
Assert.IsTrue(bag.Contains(7));
Assert.IsTrue(bag.Contains(5));
Assert.IsTrue(bag.Count == 3);
flag = this.KnapsackRecursive(weights, 27, knapsack: out bag);
Assert.IsFalse(flag);
flag = this.KnapsackRecursive(weights, 11, knapsack: out bag);
Assert.IsTrue(flag);
Assert.IsTrue(bag.Contains(11));
Assert.IsTrue(bag.Count == 1);
flag = this.KnapsackRecursive(weights, 5, knapsack: out bag);
Assert.IsTrue(flag);
Assert.IsTrue(bag.Contains(5));
Assert.IsTrue(bag.Count == 1);
}
Вот простая рекурсивная реализация (не очень эффективная, но легко понятная). Он написан на Python, OP запрашивает реализацию Java, но перенести его на Java не должно быть слишком сложно, это все равно что смотреть на псевдокод.
Основная функция объявляет три параметра: V - массив значений, W - массив весов, а C - вместимость ранца.
def knapsack(V, W, C):
return knapsack_aux(V, W, len(V)-1, C)
def knapsack_aux(V, W, i, aW):
if i == -1 or aW == 0:
return 0
elif W[i] > aW:
return knapsack_aux(V, W, i-1, aW)
else:
return max(knapsack_aux(V, W, i-1, aW),
V[i] + knapsack_aux(V, W, i-1, aW-W[i]))
Алгоритм максимизирует стоимость предметов, добавляемых в рюкзак, возвращая максимальное значение, достижимое при заданных весах
public class Knapsack {
public int[] arr = {11,8,7,6,5};
public int[] retArr = new int[5];
int i = 0;
public boolean problem(int sum, int pick) {
if(pick == arr.length) {
return false;
}
if(arr[pick] < sum) {
boolean r = problem(sum - arr[pick], pick+1);
if(!r) {
return problem(sum, pick+1);
} else {
retArr[i++] = arr[pick];
return true;
}
} else if (arr[pick] > sum) {
return problem(sum, pick+1);
} else {
retArr[i++] = arr[pick];
return true;
}
}
public static void main(String[] args) {
Knapsack rk = new Knapsack`enter code here`();
if(rk.problem(20, 0)) {
System.out.println("Success " );
for(int i=0; i < rk.retArr.length; i++)
System.out.println(rk.retArr[i]);
}
}
}
Еще одна реализация динамического программирования на Java. Я всегда чувствую, что нисходящий DP, используя памятку, гораздо легче понять, чем восходящий DP.
Полный, понятный, исполняемый код, использующий данные из этого примера из Википедии:
import java.util.ArrayList;
import java.util.Collections;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
public class Knapsack {
private static final List<Item> ITEMS = new ArrayList<>();
private static final Map<Integer, Bag> CACHE = new HashMap<>();
private static final boolean FINITE_ITEMS = true; //whether an item can be added more than once
public static void main(String[] args) {
ITEMS.add(new Item(4, 12, "GREEN"));
ITEMS.add(new Item(2, 2, "CYAN"));
ITEMS.add(new Item(2, 1, "GREY"));
ITEMS.add(new Item(1, 1, "ORANGE"));
ITEMS.add(new Item(10, 4, "YELLOW"));
Bag best = bestBagForCapa(15);
System.out.println(best.toString());
}
public static Bag bestBagForCapa(int capa) {
if (CACHE.containsKey(capa)) return CACHE.get(capa);
if (capa < 0) return null;
if (capa == 0) return new Bag(0, 0);
int currentWeight = -1;
int currentValue = -1;
String newItem = null;
List<String> previousItems = null;
for (Item p : ITEMS) {
Bag previous = bestBagForCapa(capa - p.weight);
if (previous == null) continue;
int weightSoFar = previous.weight;
int valueSoFar = previous.value;
int nextBestValue = 0;
Item candidateItem = null;
for (Item candidate : ITEMS) {
if (FINITE_ITEMS && previous.alreadyHas(candidate)) continue;
if (weightSoFar + candidate.weight <= capa && nextBestValue < valueSoFar + candidate.value) {
candidateItem = candidate;
nextBestValue = valueSoFar + candidate.value;
}
}
if (candidateItem != null && nextBestValue > currentValue) {
currentValue = nextBestValue;
currentWeight = weightSoFar + candidateItem.weight;
newItem = candidateItem.name;
previousItems = previous.contents;
}
}
if (currentWeight <= 0 || currentValue <= 0) throw new RuntimeException("cannot be 0 here");
Bag bestBag = new Bag(currentWeight, currentValue);
bestBag.add(previousItems);
bestBag.add(Collections.singletonList(newItem));
CACHE.put(capa, bestBag);
return bestBag;
}
}
class Item {
int value;
int weight;
String name;
Item(int value, int weight, String name) {
this.value = value;
this.weight = weight;
this.name = name;
}
}
class Bag {
List<String> contents = new ArrayList<>();
int weight;
int value;
boolean alreadyHas(Item item) {
return contents.contains(item.name);
}
@Override
public String toString() {
return "weight " + weight + " , value " + value + "\n" + contents.toString();
}
void add(List<String> name) {
contents.addAll(name);
}
Bag(int weight, int value) {
this.weight = weight;
this.value = value;
}
}
def knpsack(weight , value , k , index=0 , currweight=0):
if(index>=len(weight)):
return 0
take = 0
dontake = 0
if(currweight+weight[index] <= k):
take = value[index] +
knpsack(weight,value,k,index+1,currweight+weight[index])
dontake = knpsack(weight,value,k,index+1,currweight)
return max(take,dontake)
Вот еще один
static int[] values = new int[] {1,3,5,6};
static int[] weights = new int[] {2,3,4,5};
static int W = 8;
private static int calculate(int i, int W, int cur) {
// this second check on wts is required so that if there is no space if we try this weight, dont proceed
if (i == values.length || W - weights[i] <= 0) return cur;
return Math.max(calculate(i+1, W, cur), calculate(i+1, W - weights[i], cur + values[i]));
}
public static void main(String[] args) {
System.out.println(calculate(0, W, 0));
}
Вот решение Java
static int knapsack(int[] values, int[] weights, int W, int[] tab, int i) {
if(i>=values.length) return 0;
if(tab[W] != 0)
return tab[W];
int value1 = knapsack(values, weights, W, tab, i+1);
int value2 = 0;
if(W >= weights[i]) value2 = knapsack(values, weights, W-weights[i], tab, i+1) + values[i];
return tab[W] = (value1>value2) ? value1 : value2;
}
Проверьте это с помощью
public static void main(String[] args) {
int[] values = new int[] {894, 260, 392, 281, 27};
int[] weights = new int[] {8, 6, 4, 0, 21};
int W = 30;
int[] tab = new int[W+1];
System.out.println(knapsack(values, weights, W, tab, 0));
}
Вот простое рекурсивное решение в Java, но вы должны избегать использования рекурсии, если это возможно.
public class Knapsack {
public static void main(String[] args) {
int[] arr = new int[]{11, 8, 7, 6, 5};
find(arr,20);
}
public static boolean find( int[] arr,int total){
return find(arr,0,total);
}
private static boolean find( int[] arr,int start, int total){
if (start == arr.length){
return false;
}
int curr = arr[start];
if (curr == total){
System.out.println(curr);
return true;
}else if (curr > total || !find(arr,start+1,total-curr)){
return find(arr,start+1,total);
}
System.out.println(curr);
return true;
}
}