hdu 1114 - Piggy-Bank

╰+哭是因爲堅強的太久メ 2022-07-12 06:41 88阅读 0赞

# 地址 #

[http://acm.hdu.edu.cn/showproblem.php?pid=1114][http_acm.hdu.edu.cn_showproblem.php_pid_1114]

# 定位 #

*  动态规划
 *  完全背包问题
 *  恰好装满
 *  逆向题设

# 分析 #

*  处理恰好装满问题。
    
    数组初始化为-INF, dp\[0\]=0。
 *  逆向题设, 求最小总价值。
    
    状态转移方程变取最大值为最小值, 数组初始化为INF, 即 \+∞。
    
    这样, 若不满足恰好装满条件, INF加任意非负数恒为INF。若满足恰好装满条件, 任意非负数都小于INF, 状态更新为有效值。
    
    若最终结果仍为INF, 说明此状态未进行有效更新, 即无法组成该容量。

# 代码 #

#include <stdio.h>
    #include <stdlib.h>
    #define MAX_N 10001
    
    int weight[MAX_N];
    int value[MAX_N];
    int dp[MAX_N];
    
    int main()
    {
        int T,N,W,E,F;
        int i,j;
        scanf("%d*c",&T);
        while(T--)
        {
            scanf("%d*c",&E);
            scanf("%d*c",&F);
            scanf("%d*c",&N);
            W = F - E;
            memset(weight,0,sizeof(weight));
            memset(value,0,sizeof(value));
            memset(dp,0x7f,sizeof(dp));
            for(i=1;i<=N;i++)
            {
                scanf("%d %d*c",&value[i],&weight[i]);
            }
            dp[0] = 0;
            for(i=1;i<=N;i++)
            {
                for(j=weight[i];j<=W;j++)
                {
                    dp[j] = dp[j-weight[i]] + value[i] < dp[j] ? dp[j-weight[i]] + value[i] : dp[j];
                }
            }
            if(dp[W] == 0x7f7f7f7f)
            {
                printf("This is impossible.\n");
            }
            else
            {
                printf("The minimum amount of money in the piggy-bank is %d.\n",dp[W]);
            }
        }
        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">78MS</td> 
   <td align="center">1536K</td> 
   <td align="center">1020B</td> 
   <td align="center">c</td> 
  </tr> 
 </tbody> 
</table>

Ver 2.0 2017-2-18

[http_acm.hdu.edu.cn_showproblem.php_pid_1114]: http://acm.hdu.edu.cn/showproblem.php?pid=1114