首页 > 代码库 > hdu1114(完全背包)

hdu1114(完全背包)

 

题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=1114

 

分析:很裸的一道完全背包题,只是这里求装满背包后使得价值最少,只需初始化数组dp为inf;dp[0]=0;

        然后直接套入完全背包循环就行了。。。

 

#include <cstdio>#include <cstring>#include <cmath>#include <iostream>#include <algorithm>#include <queue>#include <cstdlib>#include <vector>#include <set>#include <map>#define LL long long#define inf 1<<30using namespace std;int p[510],w[510];int dp[10010];int main(){    int a,b,v,t,n;    scanf("%d",&t);    while(t--)    {        scanf("%d%d",&a,&b);        v=b-a;        scanf("%d",&n);        for(int i=1; i<=n; i++)            scanf("%d%d",&p[i],&w[i]);        for(int i=0; i<=v; i++)dp[i]=inf;        dp[0]=0;        for(int i=1; i<=n; i++)            for(int j=w[i]; j<=v; j++)            {                dp[j]=min(dp[j],dp[j-w[i]]+p[i]);            }        if(dp[v]!=inf)        printf("The minimum amount of money in the piggy-bank is %d.\n",dp[v]);        else        printf("This is impossible.\n");    }}
View Code

 

hdu1114(完全背包)