完全背包問(wèn)題，一個(gè)物品可以無(wú)限次的使用。還有需要注意的就是該題要求恰好裝滿背包時(shí)的最小值，初始化的時(shí)候除了f[0]=0之外，其余的為負(fù)無(wú)窮。
#include <stdio.h>
#include <string.h>
#define N 10005
#define INF 2139062144
#define MAX(a, b) (a > b ? a : b)
int c[N], w[N], f[N];
int main()
{
int t, E, F, v, n;
scanf("%d", &t);
while(t--)
{
scanf("%d %d", &E, &F);
v = F - E;
scanf("%d", &n);
for(int i = 0; i < n; i++)
{
scanf("%d %d", &w[i], &c[i]);
w[i] = -w[i];
}
memset(f, 128, sizeof(f));
f[0] = 0;
for(int i = 0; i < n; i++)
{
for(int j = c[i]; j <= v; j++)
{
f[j] = MAX(f[j], f[j - c[i]] + w[i]);
}
}
if(f[v] > -INF)printf("The minimum amount of money in the piggy-bank is %d.\n", -f[v]);
else puts("This is impossible.");
}
return 0;
}