Re: [問題] 一個感覺是 dynamic programming 的題目
看板Prob_Solve (計算數學 Problem Solving)作者Franckie ( )時間14年前 (2010/04/22 21:27)推噓0(0推 0噓 0→)留言0則, 0人參與討論串6/12 (看更多)
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
討論串 (同標題文章)
本文引述了以下文章的的內容：
完整討論串 (本文為第 6 之 12 篇)：
Prob_Solve 近期熱門文章
PTT數位生活區 即時熱門文章
