r******n
发帖数: 170 | 1 A packer of boxes in a Target warehouse is packing small radios into larger
boxes that measure 25 in. by 43 in. by 62 in. If the measurement of each
radio is 7 in. by 6 in. by 5 in., then at most how many radios can be placed
in the box?
开始以为都是按照统一的方向摆，于是只有6种permutation，于是写的code如下
http://codepad.org/N3C12UCl
后来想想应该不对，哪位高手指点下？ | g**********y
发帖数: 14569 | 2 这个是DP, solution = 480
public class StackedBox {
private int W = 5;
private int H = 6;
private int D = 7;
private int[][][] dp;
private int solve(int w, int h, int d) {
dp = new int[w+1][h+1][d+1];
for (int i=0; i<=w; i++)
for (int j=0; j<=h; j++)
for (int k=0; k<=d; k++)
dp[i][j][k] = -1;
return stack(w, h, d);
}
private int stack(int w, int h, int d) {
int[] m = new int[]{w, h, d};
Arrays.sort(m);
if (m[0] < W) return 0;
if (dp[m[0]][m[1]][m[2]] >= 0) return dp[m[0]][m[1]][m[2]];
int max = 0;
max = Math.max(max, 1 + stack(W, H, m[2]-D) + stack(W, m[1]-H, m[2]) + stack(m[0]-W, m[1], m[2]));
max = Math.max(max, 1 + stack(W, D, m[2]-H) + stack(W, m[1]-D, m[2]) + stack(m[0]-W, m[1], m[2]));
max = Math.max(max, 1 + stack(H, W, m[2]-D) + stack(W, m[1]-W, m[2]) + stack(m[0]-H, m[1], m[2]));
max = Math.max(max, 1 + stack(H, D, m[2]-W) + stack(W, m[1]-D, m[2]) + stack(m[0]-H, m[1], m[2]));
max = Math.max(max, 1 + stack(D, H, m[2]-W) + stack(D, m[1]-H, m[2]) + stack(m[0]-D, m[1], m[2]));
max = Math.max(max, 1 + stack(D, W, m[2]-H) + stack(D, m[1]-W, m[2]) + stack(m[0]-D, m[1], m[2]));
dp[m[0]][m[1]][m[2]] = max;
return max;
}
public static void main(String[] args) {
int max = new StackedBox().solve(25, 43, 62);
// int max = new StackedBox().solve(5, 6, 7);
System.out.println(max);
}
} | s******d
发帖数: 2 | 3 dp是没问题，我猜程序有点小bug吧
盒子总体积是25*43*62=66650，
一个radio的体积是5*6*7=210，
即使盒子完全利用，能装的radio是66650/21=317.4个 | g**********y
发帖数: 14569 | 4 谢谢，肯定是有条件写错了。今天可能没时间看了，欢迎各位debug.
【在 s******d 的大作中提到】
: dp是没问题，我猜程序有点小bug吧
: 盒子总体积是25*43*62=66650，
: 一个radio的体积是5*6*7=210，
: 即使盒子完全利用，能装的radio是66650/21=317.4个
|
|
