首页 > 代码库 > hduPiggy-Bank(完全背包)

hduPiggy-Bank(完全背包)

2024-07-15 13:57:00   218人阅读

  http://acm.hdu.edu.cn/showproblem.php?pid=1114

此题就是最简单的完全背包，顺序！！！

for i=1..N

    for v=0..V

        f[v]=max{f[v],f[v-cost]+weight}

#include <iostream>#include <stdio.h>#include <string.h>#include <stdlib.h>#define N 1000001int dp[10005];int main(){    int T,E,V,n;    int w[502],v[502];    scanf("%d",&T);    while(T--)    {       scanf("%d%d",&E,&V);       V=V-E;       scanf("%d",&n);       for(int i=1;i<=n;i++)       {           scanf("%d%d",&v[i],&w[i]);       }       for(int i=0;i<=V;i++)         dp[i]=N;         dp[0]=0;       for(int i=1;i<=n;i++)       {           for(int j=w[i];j<=V;j++)           {               if(dp[j-w[i]]+v[i]<dp[j])                  dp[j]=dp[j-w[i]]+v[i];           }       }       if(dp[V]==N) printf("This is impossible.\n");       else printf("The minimum amount of money in the piggy-bank is %d.\n",dp[V]);    }    return 0;}

 


联系
我们