hdu 1171 - Big Event in HDU(完全背包)

你的名字 2022-07-12 08:12 136阅读 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