The Chocolate Boy

One day Jenish goes to a chocolate shop to buy chocolates. There are $N$ chocolates, where the $i^{th}$ chocolate has a sweetness $sweet[i]$ .He only buys chocolates of type soft(he doesn't like hard chocolates). But he wants to buy chocolates such that sum of sweetness does not exceed $M$. He has one special energy. Using it, he can halve the sweetness of any chocolate present in a shop. He can use this energy at most one time. You have to find the maximum price he has to pay. 

Example:

Input:  4 4
dairymilk S 5 15
kitkat H 7 10
fivestar S 2 20
snickers S 4 17
Output: 37

Approach

Java

public class TheChocolateBoy {
    public static void main(String args[]) {
        int n = 4;
        int m = 4;
        String arr[] = { "dairymilk S 5 15", "kitkat H 7 10", "fivestar S 2 20", "snickers S 4 17" };
        int dp[][][] = new int[2][m + 1][2], i, j, cur = 1;
        for (i = 0; i < n; i++) {
            String[] s = arr[i].split(" ");
            if (s[1].equals("H"))
                continue;
            int p = Integer.parseInt(s[3]), x = Integer.parseInt(s[2]);
            for (j = 0; j <= m; j++)
                if (j < x / 2)
                    dp[cur][j][1] = dp[cur ^ 1][j][1];
                else
                    dp[cur][j][1] = Math.max(dp[cur ^ 1][j][1], dp[cur ^ 1][j - x / 2][0] + p);
            for (j = 0; j <= m; j++)
                if (j < x)
                    dp[cur][j][0] = dp[cur ^ 1][j][0];
                else {
                    dp[cur][j][1] = Math.max(dp[cur][j][1], Math.max(dp[cur ^ 1][j][1], dp[cur ^ 1][j - x][1] + p));
                    dp[cur][j][0] = Math.max(dp[cur ^ 1][j][0], dp[cur ^ 1][j - x][0] + p);
                }
            cur ^= 1;
        }
        int ans = 0;
        for (i = 0; i <= m; i++) {
            ans = Math.max(dp[cur ^ 1][i][0], ans);
            ans = Math.max(dp[cur ^ 1][i][1], ans);
        }
        System.out.println(ans);
    }
}