getting wrong answer on spoj PHIDIAS problem using dp.

I have used 3D dp in this case i.e dp[i][j][k] where dp[i][j][k] means i have to maximize utilization of (i X j) rectangle with k options and i have given the answer as w*h - dp[w][h][n].

lp(i,1,wd+1){
    lp(j,1,ht+1){
        lp(k,1,n+1){
            dp[i][j][k] = dp[i][j][k-1];
            if(i>=w[k] && j>=h[k]){
                dp[i][j][k] = max(dp[i][j][k],dp[i-w[k]][j][k] + dp[w[k]][j-h[k]][k] + w[k]*h[k]);
                dp[i][j][k] = max(dp[i][j][k],dp[i][j-h[k]][k] + dp[i-w[k]][h[k]][k] + w[k]*h[k]);
            }
        }
    }
}

i am getting wrong answer. please see it.

ya i know 2d solution, but what is wrong with this 3d. I have checked various test cases and it is giving correct answer same answer as given by your 2d solution, but what is wrong in this case. or if you can find the test case in which it gives wrong solution.

problem link: SPOJ.com - Problem PHIDIAS

Solved it using top down…U can do it using 2d dp…

int phidias(int w, int h) {
if(dp[w][h] > -1) return dp[w][h];
int &res = dp[w][h] = w * h, tmp;
for(int i = 1; i <= (w >> 1); i++) {
	tmp = phidias(i, h);
	if(tmp < res) tmp += phidias(w - i, h);
	if(tmp < res) res = tmp;
}
for(int i = 1; i <= (h >> 1); i++) {
	tmp = phidias(w, i);
	if(tmp < res) tmp += phidias(w, h - i);
	if(tmp < res) res = tmp;
}
return res;

}

cin>>W>>H>>n;
	memset(dp, -1, sizeof dp);
	for(i = 0; i < n; i++) {
		scanf("%d %d", &w[i], &h[i]);
		dp[w[i]][h[i]] = 0;
	}
	phidias(W, H));
1 Like

Its neat and clean…hope u can easily understand it.

ya i know 2d solution, but what is wrong with this 3d. I have checked various test cases and it is giving correct answer same answer as given by your 2d solution, but what is wrong in this case. or if you can find the test case in which it gives wrong solution.