地址
http://acm.hdu.edu.cn/showPRoblem.php?pid=1171
定位
動態規劃
完全背包問題
大數組
分析
AB兩學院分配一個總價值為 W 的物品集, 要求各自分得的物品價值盡量接近, 且 A≤B。
對于B學院, 等價于背包容量為 W2 的完全背包問題。
題中, 分配標準只是價值均分, 對物品種數沒有要求, 每種分一半的常規理解不是最佳的, 只關心價值即可。
與典型完全背包問題相比, 有幾點不同：
(1) 物品價值同時也是其重量。
(2) 物品數量直接給出, 而不是靠容量約束。
問題規模很大, 設計存儲空間時需精打細算。
物品種類 0<N≤50, 每種數量 0<M≤100, 每種價值 0<V≤50。
故, 物品集總價值 0<W≤250000, 背包容量 0<W2≤125000。
int value[51];int num[51];int dp[125001];鑒于 n=106 的問題規模, 不論時間復雜度還是空間復雜度都要盡可能優化。
(1) 按照0-1背包的思路求解, 相當于有 ∑mi 種物品, 時間復雜度為 O(NW∑mi)。按照完全背包優化的思路求解, 時間復雜度為 O(NW)。
選擇后者。
(2) 存儲空間為一維數組, 盡量減少空間復雜度。
代碼
#include <stdio.h>#include <stdlib.h>int value[51];int num[51];int dp[125001];int main(){ int N,V,W; int i,j,tmp; scanf("%d*c",&N); while(N > 0) { memset(value,0,sizeof(value)); memset(value,0,sizeof(num)); memset(dp,0,sizeof(dp)); V = 0; for(i=1;i<=N;i++) { scanf("%d %d*c",&value[i],&num[i]); V += value[i] * num[i]; } W = V / 2; for(i=1;i<=N;i++) { for(j=value[i];j<=W;j++) { tmp = dp[j-value[i]] + value[i]; if((tmp-dp[j])/value[i] <= num[i] && tmp > dp[j]) { dp[j] = tmp; } else { dp[j] = dp[j-1] > dp[j] ? dp[j-1] : dp[j]; } } } printf("%d %d/n",V - dp[W],dp[W]); scanf("%d*c",&N); } return 0;}性能
| Exe.Time | Exe.Memory | Code Length | Language |
| 31MS | 1900K | 998B | c |
總結
考慮到本題規模, 采用背包思路求解本身就比較勉強, 另一種解題思慮是母函數, 容稍后嘗試。
Ver 2.0 2017-2-18
