// 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];
         }
      }
 
      for (int p = 0; p <=n; p++) {
      	for (int q = 0; q <=W; q++) {
      		System.out.print(K[p][q] + ", ");
      	}
      	System.out.println();
      }
      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[]{1, 2, 3};
    int  W = 5;
    int n = val.length;
    System.out.println(knapSack(W, wt, val, n));
    }
}
/*This code is contributed by Rajat Mishra */

Ly8gQSBEeW5hbWljIFByb2dyYW1taW5nIGJhc2VkIHNvbHV0aW9uIGZvciAwLTEgS25hcHNhY2sgcHJvYmxlbQpjbGFzcyBLbmFwc2Fjawp7CiAKICAgIC8vIEEgdXRpbGl0eSBmdW5jdGlvbiB0aGF0IHJldHVybnMgbWF4aW11bSBvZiB0d28gaW50ZWdlcnMKICAgIHN0YXRpYyBpbnQgbWF4KGludCBhLCBpbnQgYikgeyByZXR1cm4gKGEgPiBiKT8gYSA6IGI7IH0KICAgICAgCiAgIC8vIFJldHVybnMgdGhlIG1heGltdW0gdmFsdWUgdGhhdCBjYW4gYmUgcHV0IGluIGEga25hcHNhY2sgb2YgY2FwYWNpdHkgVwogICAgc3RhdGljIGludCBrbmFwU2FjayhpbnQgVywgaW50IHd0W10sIGludCB2YWxbXSwgaW50IG4pCiAgICB7CiAgICAgICAgIGludCBpLCB3OwogICAgIGludCBLW11bXSA9IG5ldyBpbnRbbisxXVtXKzFdOwogICAgICAKICAgICAvLyBCdWlsZCB0YWJsZSBLW11bXSBpbiBib3R0b20gdXAgbWFubmVyCiAgICAgZm9yIChpID0gMDsgaSA8PSBuOyBpKyspCiAgICAgewogICAgICAgICBmb3IgKHcgPSAwOyB3IDw9IFc7IHcrKykKICAgICAgICAgewogICAgICAgICAgICAgaWYgKGk9PTAgfHwgdz09MCkKICAgICAgICAgICAgICAgICAgS1tpXVt3XSA9IDA7CiAgICAgICAgICAgICBlbHNlIGlmICh3dFtpLTFdIDw9IHcpCiAgICAgICAgICAgICAgICAgICBLW2ldW3ddID0gbWF4KHZhbFtpLTFdICsgS1tpLTFdW3ctd3RbaS0xXV0sICBLW2ktMV1bd10pOwogICAgICAgICAgICAgZWxzZQogICAgICAgICAgICAgICAgICAgS1tpXVt3XSA9IEtbaS0xXVt3XTsKICAgICAgICAgfQogICAgICB9CiAgICAgIAogICAgICBmb3IgKGludCBwID0gMDsgcCA8PW47IHArKykgewogICAgICAJZm9yIChpbnQgcSA9IDA7IHEgPD1XOyBxKyspIHsKICAgICAgCQlTeXN0ZW0ub3V0LnByaW50KEtbcF1bcV0gKyAiLCAiKTsKICAgICAgCX0KICAgICAgCVN5c3RlbS5vdXQucHJpbnRsbigpOwogICAgICB9CiAgICAgIHJldHVybiBLW25dW1ddOwogICAgfQogCiAgIAogICAgLy8gRHJpdmVyIHByb2dyYW0gdG8gdGVzdCBhYm92ZSBmdW5jdGlvbgogICAgcHVibGljIHN0YXRpYyB2b2lkIG1haW4oU3RyaW5nIGFyZ3NbXSkKICAgIHsKICAgICAgICBpbnQgdmFsW10gPSBuZXcgaW50W117NjAsIDEwMCwgMTIwfTsKICAgIGludCB3dFtdID0gbmV3IGludFtdezEsIDIsIDN9OwogICAgaW50ICBXID0gNTsKICAgIGludCBuID0gdmFsLmxlbmd0aDsKICAgIFN5c3RlbS5vdXQucHJpbnRsbihrbmFwU2FjayhXLCB3dCwgdmFsLCBuKSk7CiAgICB9Cn0KLypUaGlzIGNvZGUgaXMgY29udHJpYnV0ZWQgYnkgUmFqYXQgTWlzaHJhICov