T组数据,每组给定背包体积V(10000),物品种类N(500),每种物品的价值value和体积volume. 装满背包,求最小价值,存在无解.
这个题使用的是从前转移,注意满包问题需要设置非法状态,从前转移的非法状态同理continue. 这个题求最小值,所以非法状态设置为INT_MAX.
int t=read();
while(t--)
{
int v1=read(),v2=read(),v=v2-v1,n=read();
for(
int i=
1;i<=n;i++)
value[i]=read(),volume[i]=read();
for(
int i=
1;i<=v;i++)
dp[i]=INT_MAX;
dp[
0]=
0;
for(
int i=
1;i<=n;i++)
for(
int j=volume[i];j<=v;j++)
{
if(dp[j-volume[i]]==INT_MAX)
continue;
dp[j]=min(dp[j],dp[j-volume[i]]+value[i]);
}
if(dp[v]==INT_MAX)
printf(
"This is impossible.\n");
else
printf(
"The minimum amount of money in the piggy-bank is %d.\n",dp[v] );
}
