これは私の仕事です
ナップザック問題は、コンピューター サイエンスの古典です。最も単純な形式では、ナップザックが指定された総重量になるように、さまざまな重量のアイテムをナップザックに収めようとします。すべての項目に当てはまる必要はありません。たとえば、ナップザックの重量を正確に 20 ポンドにしたいとします。5 つのアイテムがあり、重量は 11、8、7、6、および 5 ポンドです。アイテムの数が少ない場合、人間は検査によってこの問題を解決するのが得意です。したがって、合計が 20 になるのは、8、7、および 5 の項目の組み合わせのみであることがわかります。
このアルゴリズムをどこから書き始めればよいのか、本当にわかりません。階乗と三角形の数に適用される再帰を理解しています。しかし、私は今迷っています。
何を試しましたか？
あなたが述べた問題（再帰を使用する必要があることを示しています）を考えると、アイデアは簡単です。取ることができる各アイテムについて、それを取るかどうかを確認してください。したがって、可能なパスは 2 つだけです。
アイテムを取得すると、リストから削除され、アイテムの重量によって容量が減少します。
アイテムを取らないときは、リストから削除しますが、容量は減らしません。
再帰呼び出しがどのように見えるかを出力すると役立つ場合があります。この場合、次のようになります。
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] は 2 回呼び出されることに注意してください。1 回は容量 20 (11 を使用しなかったため) で、もう 1 回は容量 9 (11 を使用したため) で呼び出されます。
したがって、ソリューションへのパス：
11 未使用、20 の容量で [8 7 6 5] を呼び出す
8 が取られ、キャパシティ 12 (20 - 8) で [7 6 5] を呼び出します
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#Dynamic_programming
この問題は、基本的に単純化のために従来のナップザックの問題を修正したものです(重みに対応する値/利点はありません) (実際の場合: http://en.wikipedia.org/wiki/Knapsack_problem , 0/1 Knapsack - に関するいくつかの説明Wiki の疑似コード、ナップザック問題が NP 完全であることを理解する方法は?、ナップザック問題が疑似多項式である理由は?、http://www.geeksforgeeks.org/dynamic-programming-set-10-0-1-knapsack-problem / )。
C# でこれを解決する 5 つのバージョンを次に示します。
version1 : 動的計画法の使用 (表形式 - すべての合計問題の解を熱心に見つけて最終的な問題に到達する) - O(n * W)
バージョン 2 : DP を使用するがメモ化バージョン (怠惰 - 必要なものの解決策を見つけるだけ)
バージョン 3再帰を使用して重複した部分問題と最適な部分構造を示す
バージョン 4再帰的 (ブルート フォース) - 基本的に受け入れられた回答
バージョン 5 #4 のスタックを使用 (末尾再帰の削除のデモンストレーション)
version1 : 動的計画法の使用 (表形式 - すべての合計問題の解を熱心に見つけて最終的な問題に到達する) - 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;
}
version 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);
}
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]);
}
}
}
これは単純な再帰的な実装です (あまり効率的ではありませんが、従うのは簡単です)。それは Python であり、OP は Java 実装を求めていますが、それを Java に移植することはそれほど難しくないはずです。疑似コードを見るようなものです。
main 関数は 3 つのパラメーターを宣言します。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]))
アルゴリズムは、ナップザックに追加されたアイテムの値を最大化し、指定された重みで達成可能な最大値を返します
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;
}
}
ここに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;
}
}