作者Franckie ( )
看板Prob_Solve
标题Re: [问题] 一个感觉是 dynamic programming 的题目
时间Thu Apr 22 21:27:21 2010
my java implementation
public int maxHeight(int[] weight, int[] capacity) {
int N = weight.length;
for(int i = 0; i < N; ++i){
for(int j =i +1; j < N;++j){
if(weight[j]+capacity[j]<=weight[i]+capacity[i]){
int t = weight[i];
weight[i] = weight[j];
weight[j]=t;
t = capacity[i];
capacity[i] = capacity[j];
capacity[j] = t;
}
}
}
int[] dp = new int[N+1];
for (int i = 0; i <= N; i++)
dp[i] = Integer.MAX_VALUE;
dp[0] = 0;
int max = 0;
for (int i = 0; i < N; i++) {
for (int j = max + 1; j > 0; j--) {
if (capacity[i] >= dp[j - 1]
&& dp[j - 1] + weight[i] < dp[j]) {
dp[j] = dp[j - 1] + weight[i];
if (j > max)
max = j;
}
}
}
return max;
}
※ 引述《DJWS (...)》之铭言：
: ※ 引述《locomotion (locomotion)》之铭言：
: : 1.先将所有箱子依载重量由小到大排 (Sorting:O(nlogn))
: : 2.依载重量由小到大放进list
: : a.如果累积的重量比当前箱子的载重量小，将箱子放进list
: : b.如果累积的重量超过当前箱子的载重量
: : 将目前list中最重的箱子拿走
: 这里举个反例。
: 这是一组合理的答案：
: 重量 载重量 累积重量
: 1 1 0
: 20 10 1
: 3 37 21
: 152 47 24
: 10 490 176
: 500 401 186
: 1 999 686
: 2 998 687
: 这是用载重量排序之後的情况，有个地方叠不上去....
: 重量 载重量 累积重量
: 1 1 0
: 20 10 1
: 3 37 21
: 152 47 24
: 500 401 176
: 10 490 676 ＜－－－－ 载重量小於累积重量，需舍弃某个箱子。
: 2 998 686
: 1 999 688
--
※ 发信站: 批踢踢实业坊(ptt.cc)
◆ From: 220.142.16.62