どうすれば解決できますか？ KnapSack - 値はすべて同じですが、お互いのオブジェクトに3つの重みがあります

Question

私の運動を解決することに問題があります。私はダイナミックなプログラミングとアルゴリズムについて読んで、私の運動は「特定のナップザックの問題」だと思います。 brute forceメソッドで解決しましたが、動的プログラミングでは解決できません。

私は重量300トンの船（ナップザック）を持っています。 3つの物質（X、Y、Z）を持つ結晶があります - それぞれの物質は重量を持ち、すべての結晶は同じ値を持っています。私はできるだけ多くの結晶を梱包する必要がありますが、パックされたすべての結晶の物質の比率は1：1：1でなければなりません。しかし、例えば、私は3つの結晶が1：1：1の比率で最も多くのトンを与え、8つの結晶が同じ数のトンを与える場合（2つの他の結晶の組合せが最も多くのトンを与える）、私は最低数の結晶との組み合わせ。

私はブルートフォース法で解決しました - 私はすべての組み合わせの配列のリストを作成しました。次に、私は1：1：1の割合でこれらの組み合わせを見つけました。次に、最も多くのトンを与え、同じ数の同じトン数の2つ以上の組み合わせがある場合、最も少ない数の結晶を有する組み合わせを見いだした。私はテストをチェックし、良いスコアを返しました ダイナミックプログラミングでどのように解決できますか？/私を助ける人はいますか？

例について

I 10の結晶を有する：

1) X =2 Y =3 Z =4 
2) X =5 Y=10 Z =2 
3) X =3 Y =3 Z =3 
4) X =1 Y =0 Z =6 
5) X =9 Y=12 Z =4 
6) X =1 Y =1 Z =1 
7) X =2 Y =1 Z=0 
8) X =1 Y =2 Z =3 
9) X =1 Y =1 Z =1 
10) X =4 Y =3 Z =3 

溶液である：最大27トン5つの結晶と（番号：1、3、6、7及び9）

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 */ 

出典：​​