完全背包。
要点：
1.要求价值的最小值
2.要求背包正好装满
#include<stdio.h>//pku1384
#include<string.h>
#include<stdlib.h>
#define LENEF 10010
#define LENNP 510
#define MAX 1000000000
int f[LENEF];
int N, T, E, F;
int P[LENNP], W[LENNP];
int min(int a, int b)
{
if(a < b)
return a;
return b;
}
void CPack()
{
int i, j;
int V = F - E;
for(i = 1; i <= V; i++)
f[i] = MAX;
f[0] = 0;
for(i = 1; i <= N; i++)
{
for(j = W[i]; j <= V; j++)
f[j] = min(f[j], f[j - W[i]] + P[i]);
}
}
int main()
{
int i, j;
scanf("%d", &T);
for(int k = 0; k < T; k++)
{
scanf("%d%d%d", &E, &F, &N);
for(i = 1; i <= N; i++)
scanf("%d%d", &P[i], &W[i]);
//
//printf("E = %d F = %d N = %d\n", E, F, N);
//
CPack();
if(f[F - E] != MAX)
printf("The minimum amount of money in the piggy-bank is %d.\n", f[F - E]);
else
printf("This is impossible.\n");
}
}
posted on 2012-05-09 18:23
小鼠标 阅读(133)
评论(0) 编辑 收藏 引用 所属分类:
DP