2
\$\begingroup\$

Problem Statement:

I am given a set of prices for \$n\$ items I have to find out what is the maximum value I can get with \$M\$ money by selecting exactly \$C\$ items without exceeding the amount of money I have. Obviously \$C \leq N\$.

Solution:

The code for the above problem is developed using the suggestions taken from here. The code in java is given below:

public class KnpMD {


    public static void main(String[] args) {

        int items[] = {4,6,9,10};
        int M = 12;
        int C = 2;

        int dp[][][] = new int[items.length+1][M+1][C+1];

        for(int i = 0; i < items.length+1; i++) {
            for(int j = 0; j < M+1; j++) {
                for(int k = 1; k <= C; k++) {
                    dp[i][j][k] = -1;
                }
            }
        }

        for(int i = 0; i < items.length; i++) {
            for(int j = 1 ; j < M + 1; j++) {

                for(int k = 1; k <= C; k++) {

                    dp[i+1][j][k] = dp[i][j][k];// to Copy all previous optimal states found.

                    if(items[i] > j)
                        continue;

                    if(dp[i][j-items[i]][k-1] != -1)
                        dp[i+1][j][k] = Math.max(dp[i+1][j][k],
                                dp[i][j-items[i]][k-1] + items[i]);
                }
            }


        }

        System.out.println(dp[items.length][M][C]);
    }
}

What are some of the improvments I can add to this code? I am unable to follow the optimzations suggested in the answer linked above.

Can someone tell me what is the meaning of the statement(linked in the above answer)

In the preceding formulae, we retrieved the optimal solution which consisted of no more than (k−1)(k−1) items among the first (j−1)(j−1) as Ti,j−1,k−1Ti,j−1,k−1. However, it should be clear that this is precisely equal to maxp=0,j−1{Ti,p}maxp=0,j−1{Ti,p} just by using the original table!! ie., the optimal solution with no more than kk items can be also retrieved by considering the optimal solutions with 1 item, 2 items, 3 items, ... (j−1)(j−1) items ...

Any other improvments would be greatly appreciated.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.