#include
#define min(x,y) x>cas;
while(cas--)
{
int tal,j,i,w[MAX],p[MAX],empty,full,n;
cin>>empty>>full;
tal=full-empty;
cin>>n;
for(i=1;i<=n;i++)
cin>>p[i]>>w[i];
init();
dp[0]=0;
for(i=1;i<=n;i++)
for(j=w[i];j<=tal;j++)
{
dp[j]=min(dp[j],dp[j-w[i]]+p[i]);
}
if(dp[tal]==INF)
cout<<"This is impossible."<
HDU1114_DP_完全背包
题目大意:
让你输入空的存钱罐的质量empty,还有存满时的质量full。
然后输入n,接下来有n组,每组输入p,w.代表n种硬币,p是每种的价格,w是每种的质量。
要求求出这个存钱罐的可能最小钱数。
解题思路:
属于背包九讲中的完全背包,以存钱罐中钱的质量tal=full-empty,不过特殊的就是这种背包必须把背包填满,即最终放的硬币必须是刚刚好为tal.01背包中已经讲了额,只需要再初始化的时候把dp[0]初始化为0,其它的初始化为负无穷即可。但是考虑到这道题目是要求最小的钱数的。所以初始化的时候,要初始化为正无穷。
代码: