重溫了下 背包九講 不僅發(fā)現(xiàn)了其中的一些錯(cuò)誤 也發(fā)現(xiàn)了這篇文章的局限性，例如這個(gè)題。。。做完之后 我對(duì)背包的概念又模糊了。。。
#include<iostream>
using namespace std;
int dp[10001];
int w[10001];
int v[10001];
int main()
{
int t;
int e,f;
int n;
int ww;
scanf("%d",&t);
int i,j,k;
for(i=1;i<=t;i++)
{
scanf("%d%d",&e,&f);
ww=f-e;
scanf("%d",&n);
for(j=1;j<=n;j++)
scanf("%d%d",&v[j],&w[j]);
memset(dp,-1,sizeof(dp));
dp[0]=0;
for(j=1;j<=n;j++)
{
for(k=0;k<=ww-w[j];k++)
{
if(dp[k]!=-1)
{
if(dp[k+w[j]]==-1)
dp[k+w[j]]=dp[k]+v[j];
else
dp[k+w[j]]=min(dp[k+w[j]],dp[k]+v[j]);
}
}
}
if(dp[ww]==-1)
printf("This is impossible.\n");
else
printf("The minimum amount of money in the piggy-bank is %d.\n",dp[ww]);
}
return 0;
}