poj 3628 - Bookshelf 2

àì夳堔傛蜴生んèń 2022-06-08 07:21 88阅读 0赞

# 1. 地址 #

[http://poj.org/problem?id=3628][http_poj.org_problem_id_3628]

# 2. 定位 #

*  动态规划
 *  0-1背包

# 3. 分析 #

## 3.1 0-1背包的细微变形 ##

相对于典型的0-1背包，本题进行了细微变形：

*  重量相当于价格，即 weight\[i\]=value\[i\]
 *  背包容量隐藏，本题中的背包容量为总高度S
 *  求解在 dp\[i\]−B>=0 条件下， dp\[i\]−B 的最小值

本题按照典型的0-1背包求解，区别仅在输入数据处理和问题结果输出上。

# 4. 代码 #

#include <stdio.h>
    #include <stdlib.h>
    
    int weight[21];
    
    int main()
    {
        int N,B;
        int i,j,sum = 0;
        int* dp;
    
        scanf("%d*c",&N);
        scanf("%d*c",&B);
        memset(weight,0,sizeof(weight));
        for(i=1; i<=N; i++)
        {
            scanf("%d*c",&weight[i]);
            sum += weight[i];
        }
        dp = (int*)calloc(sum,sizeof(int));
        memset(dp,0,sizeof(dp));
        for(i=1; i<=N; i++)
        {
            for(j=sum; j>=weight[i]; j--)
            {
                dp[j] = dp[j-weight[i]] + weight[i] > dp[j] ? dp[j-weight[i]] + weight[i] : dp[j];
            }
        }
        for(i=B; dp[i]<B; i++)
        {
        }
        printf("%d\n",dp[i]-B);
        return 0;
    }

# 5. 性能 #

<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">0MS</td> 
   <td align="center">860K</td> 
   <td align="center">636B</td> 
   <td align="center">c</td> 
  </tr> 
 </tbody> 
</table>

# 6. 优化 #

## 6.1 数据规模的遐想 ##

虽然0-1背包顺利解决了问题，但本题的数据规模令人充满遐想。物品数 1≤N≤20，小的不能再小的数据规模，相比之下，单个高度 1≤H≤1,000,000，显得很大了。

最大背包容量会达到20,000,000，并且，由于极小的物品总数，背包中存在大量的冗余存储和重复计算。这些值得思考，本题将如何进行优化？

Ver 1.0 2017-9-18

[http_poj.org_problem_id_3628]: http://poj.org/problem?id=3628