特定のナップザックアルゴリズム

Question

私は、特定のナップザックアルゴリズムの問​​題を解決することに問題があります。私にいくつかのヒントを与えたり、助けてくれる人はいますか？私はブルートフォースの方法で解決しましたが、実行時間は非常に長いです（私はすべての可能な組み合わせをチェックして、最良の解決策を取っています）。ダイナミックプログラミングや欲張りアルゴリズムで解決する必要があります（ただし、DPでは良い）。私はそれについて多くを読んで、私はそれで解決策を見つけることができません; /それは困難な運動です。 HERE IS description of my exercise

HERE ARE TESTS FOR THIS EXERCISE

Answer 1

徹底的ナップザック問題を説明し、インターネット上でいくつかの良いチュートリアルがあります。

具体的には、問題と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 */ 

出典：​​