[]
[我要回覆]
1
|
|||||
|
|||||
樓主 梅菊客 
 發送站內信 |
有一名貨車司機要將倉庫中的商品運到賣場，每件商品的價值與重量都不同，司機想在貨車可承受的最大重量下，將價值最高的幾樣商品運到賣場。 ( 貨車負重為 20) ( 貨車與倉庫請以 stack 實作 ) 選擇要運送商品的規則是： 1. 若目前商品在負重範圍內，則直接將商品運上貨車。 2. 若目前商品運上貨車後超過負重，則檢查貨車上最後一項商品 a) 若其價值 / 重量比例低於要運上車的商品，則不選此項商品。 b) 若其價值 / 重量比例高於要運上車的商品，則將貨車上最後一項商品的物品替換成目前商品 輸入說明 ： 第一行輸入為倉庫中的 商品 數量， 第二行以後每行是依序放進倉庫堆疊中每件 商品 的價值與重量。 輸出說明 ： 輸出為貨車上的物品總價值及物品總重量。 範例 ： 輸入範例 3/5(價值/重量) 6/8(價值/重量) 4/1(價值/重量) 9/2(價值/重量) 8/8(價值/重量) 輸出範例 27/19(價值/重量) #include <stdio.h> int main() { int n; while(scanf("%d", &n) == 1) { int sk1[100], sk2[100]; int idx = -1, i; int tot = 0, p = 0, v, w; int vv[100], ww[100]; for(i = n-1; i >= 0; i--) scanf("%d %d", &vv[i], &ww[i]); for(i = 0; i < n; i++) { v = vv[i], w = ww[i]; if(tot+w <= 20) { ++idx; sk1[idx] = v, sk2[idx] = w; tot += w, p += v; } else { if((double)sk1[idx]/sk2[idx] > (double)v/w) continue; if((double)sk1[idx]/sk2[idx] < (double)v/w) { tot -= sk2[idx], p -= sk1[idx]; sk1[idx] = v, sk2[idx] = w; tot += w, p += v; } } } printf("%d %d\n", p, tot); } return 0; } |
||||
0
2
18
2
