import java.util.*;

public class knap01SpaceSaving 
{
    public static void main(String[] a) 
    {
        // Random knapsack for checking methods against each other
        // Number of items
        int N = 1000;
        
        // Item descriptions
        vals = new int[N];
        weight = new int[N];
        
        // Capacity of sack
        int cap = 500;
        
        // Generate random values
        for (int i = 0; i < N; i++) 
        {
            vals[i] = (int)(Math.random() * 1000);
            weight[i] = (int)(Math.random() * cap) + 1;
        }
        
        /*
        // Method for doing custom knap sack items
        vals = new int[]{10,1,13,5,7};
        weight = new int[]{9, 2, 8, 5, 6};
        
        // Capacity of sack
        int cap = 18;
        */
        
        // ----------------------------------
        //           Recursive DP
        // ----------------------------------
        // Create the memo table
        memo = new int[cap + 1][vals.length + 1];
        
        // Fill the table with the sentinel
        for (int[] tmp : memo)
            Arrays.fill(tmp, SENT);
        
        // Compute the maximum value for the given capacity using the
        // recursive method
        System.out.println(f(cap, 0));
        
        
        // ----------------------------------
        //       Space Saving Method 1
        // ----------------------------------
        // Space Saving 1 (2 arrays and swapping)
        // Initialize the memory for the two rows
        int[] firstArr = new int[cap + 1]; // Most recent values
        int[] secondArr = new int[cap + 1]; // Values to update
        
        // The number of items
        int n = vals.length;
        
        // Loop through each item and try taking it
        for (int i = 0; i < n; i++) 
        {
            // Don't take the item
            for (int j = 0; j < cap + 1; j++) 
            {
                secondArr[j] = firstArr[j];
            }
            
            // Try taking the item for each capacity
            for (int j = 0; j < cap + 1; j++) 
            {
                // Bounds checking
                if (j + weight[i] < cap + 1) 
                {
                    // Check if the sum of the values for the updated weight 
                    // is improved using the current item
                    if (secondArr[j + weight[i]] < firstArr[j] + vals[i]) 
                    {
                        secondArr[j + weight[i]] = firstArr[j] + vals[i];
                    }
                }
            }
            
            // Swap the arrays
            int[] tmp = firstArr;
            firstArr = secondArr;
            secondArr = tmp;
        }
        
        // Print the result
        System.out.println(firstArr[cap]);
        
        
        // ----------------------------------
        //       Space Saving Method 2
        // ----------------------------------
        // Initialize memory
        firstArr = new int[cap + 1];
        
        // Store the number of items
        n = vals.length;
        
        // Loop through each item
        for (int i = 0; i < n; i++) 
        {
            // For each capacity check if the item can improve the solution
            // This is done backwards to prevent updating already updated values
            for (int j = cap + 1; j >= 0; j--) 
            {
                // Bounds checcking
                if (j + weight[i] < cap + 1) 
                {
                    // Check if we can improve the answer
                    if (firstArr[j + weight[i]] < firstArr[j] + vals[i]) 
                    {
                        firstArr[j + weight[i]] = firstArr[j] + vals[i];
                    }
                }
            }
        }
        
        // Print the result
        System.out.println(firstArr[cap]);
    }
    
    public static int[] vals, weight;
    public static int[][] memo;
    public static int SENT = -1;
    
    public static int f(int cap, int index) 
    {
        
        // Overfilled 
        if (cap < 0 )
            return -987654321;
            
        // Check if computed previously
        if (memo[cap][index] != SENT)
            return memo[cap][index];
        
        // Check end of the list
        if (index == vals.length)
            return 0;
        
        // Take item
        int first = f(cap - weight[index], index + 1) + vals[index];
        
        // Don't take
        int second = f(cap, index + 1);
        
        if (first < second)
            memo[cap][index] = second;
        else
            memo[cap][index] = first;
        
        return memo[cap][index];
    }
}