地址
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,,sizeof(weight));
memset(value,,sizeof(value));
memset(dp,,sizeof(dp));
for(i=;i<=N;i++)
{
scanf("%d %d*c",&value[i],&weight[i]);
}
dp[] = ;
for(i=;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] == )
{
printf("This is impossible.\n");
}
else
{
printf("The minimum amount of money in the piggy-bank is %d.\n",dp[W]);
}
}
return ;
}
性能
Exe.Time | Exe.Memory | Code Length | Language |
---|---|---|---|
78MS | 1536K | 1020B | c |
Ver 2.0 2017-2-18