徹底的ナップザック問題を説明し、インターネット上でいくつかの良いチュートリアルがあります。
具体的には、問題とDPアプローチが完全に説明されているthis specific oneをお勧めします。これには、Javaを含む3つの異なる言語のソリューションが含まれます。
// A Dynamic Programming based solution for 0-1 Knapsack problem
class Knapsack
{
// A utility function that returns maximum of two integers
static int max(int a, int b) { return (a > b)? a : b; }
// Returns the maximum value that can be put in a knapsack of capacity W
static int knapSack(int W, int wt[], int val[], int n)
{
int i, w;
int K[][] = new int[n+1][W+1];
// Build table K[][] in bottom up manner
for (i = 0; i <= n; i++)
{
for (w = 0; w <= W; w++)
{
if (i==0 || w==0)
K[i][w] = 0;
else if (wt[i-1] <= w)
K[i][w] = max(val[i-1] + K[i-1][w-wt[i-1]], K[i-1][w]);
else
K[i][w] = K[i-1][w];
}
}
return K[n][W];
}
// Driver program to test above function
public static void main(String args[])
{
int val[] = new int[]{60, 100, 120};
int wt[] = new int[]{10, 20, 30};
int W = 50;
int n = val.length;
System.out.println(knapSack(W, wt, val, n));
}
}
/*This code is contributed by Rajat Mishra */
出典:
ここにあなたの質問では、テキストとしてあなたの説明とテストのテキストを投稿してください。しかし、それらを使っても、具体的な質問をしていることを絞り込む必要があります。「どうやってやるのか」は具体的なものではありません。 –
あなたのコード、あなたが直面しているエラー、あなたが直面している問題が何であるかを記入してください。より一般的なガイドラインについては、[私の答え](http://stackoverflow.com/a/40475391/2679529)をご覧ください。 –