hdu-1114 Piggy-Bank---完全背包-白红宇

hdu-1114 Piggy-Bank---完全背包

阅读量：6795 次

发布时间：2019-06-26

本文共 1141 字，大约阅读时间需要 3 分钟。

题目链接：

题目大意：

给出小猪钱罐的重量和装满钱后的重量，然后是几组数据，每组数据包括每种钱币的价值与重量

要求出重量最少能装满钱罐时的最大价值

思路：

完全背包裸题，dp[j] = min(dp[j], dp[j-w[i]]+v[i])

注意dp数组开的范围，一开始开小了，一直WA

1 #include
     
       2 #include
      
        3 #include
       
         4 #include
        
          5 #include
         
           6 #include
          
            7 #include
           
             8 #include
             9 #include
             
              10 #include
              
               11 using namespace std;12 typedef pair
               
                 Pair;13 typedef long long ll;14 const int INF = 0x3f3f3f3f;15 int T, n, m, minans;16 const int maxn = 1e3 + 10;17 int dir[4][2] = { 1,0,0,1,-1,0,0,-1};18 int w[maxn], v[maxn];19 int dp[100000];20 int main()21 {22 scanf("%d", &T);23 while(T--)24 {25 scanf("%d%d", &n, &m);26 m -= n;27 scanf("%d", &n);28 for(int i = 0; i < n; i++)scanf("%d%d", &v[i], &w[i]);29 memset(dp, INF, sizeof(dp));30 dp[0] = 0;31 for(int i = 0; i < n; i++)32 {33 for(int j = w[i]; j <= m; j++)34 dp[j] = min(dp[j], dp[j - w[i]] + v[i]);35 }36 if(dp[m] >= 1000000)37 printf("This is impossible.\n");38 else printf("The minimum amount of money in the piggy-bank is %d.\n", dp[m]);39 }40 return 0;41 }