hdu 1171 - Big Event in HDU(完全背包) 待我称王封你为后i 2022-07-12 08:12 81阅读 0赞 # 地址 # [http://acm.hdu.edu.cn/showproblem.php?pid=1171][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; } # 性能 # <table> <thead> <tr> <th align="center">Exe.Time</th> <th align="center">Exe.Memory</th> <th align="center">Code Length</th> <th align="center">Language</th> </tr> </thead> <tbody> <tr> <td align="center">31MS</td> <td align="center">1900K</td> <td align="center">998B</td> <td align="center">c</td> </tr> </tbody> </table> # 总结 # 考虑到本题规模, 采用背包思路求解本身就比较勉强, 另一种解题思虑是母函数, 容稍后尝试。 Ver 2.0 2017-2-18 [http_acm.hdu.edu.cn_showproblem.php_pid_1171]: http://acm.hdu.edu.cn/showproblem.php?pid=1171
还没有评论,来说两句吧...