HDU 1114 is a complete knapsack. If you take out the knapsack function separately, you will get WA. If you write it into the main function, you will get AC. Why?

  c++, question

Title description

Address:http://acm.hdu.edu.cn/showpro …

Question: Small pot friends save money to do things by putting money into pig piggy banks. Unless the piggy bank is smashed, the money cannot be taken out. In order to know if he has saved enough money, weigh the piggy bank. Then tell the weight and value of each coin and ask how much money there is in the piggy bank.

The Source of the Topic and Its Ideas

Conventional complete backpack problem, the problem is as shown in the title,complete_pack()Write inmain()Can AC, write alone will WA.

Related codes

//here will becomplete_pack()Write it out separately and it will be WA.

#include <iostream>
 #include <cstring>
 #include <cstdio>
 using namespace std;
 const int maxn = 11111, INF = 0x3f3f3f3f;
 int dp[maxn];
 int total_cost, total_kind;
 struct Obj
 {
 int value, cost;
 };
 Obj arr[maxn];
 void complete_pack()
 {
 memset(dp, 0x3f, sizeof(dp));
 dp[0] = 0;
 for (int i = 1;   i <= total_kind;  i++)
 for (int j = arr[i].cost;   j <= total_cost;  j++)
 dp[j] = min(dp[j], dp[j - arr[i].cost] + arr[i].value);
 if (dp[total_cost] !  = INF)
 printf("The minimum amount of money in the piggy-bank is %d.\n", dp[total_cost]);
 else
 printf("This is impossible.\n");
 }
 int main()
 {
 freopen("in.txt", "r", stdin);
 int T;
 scanf("%d", &T);
 while (T--)
 {
 int E, F;
 scanf("%d%d", &E, &F);
 total_cost = F - E;
 int total_kind;
 scanf("%d", &total_kind);
 for (int i = 1;   i <= total_kind;  i++)
 scanf("%d%d", &arr[i].value, &arr[i].cost);
 complete_pack();
 }
 return 0;
 }

Two areas need to be amended.

  1. Usememset(dp, 0x3f, ...)After the array is initialized, the element value does not have to be0x3f3f3f3f, which depends on the compiler’s int type number of bits, only 32 bits hold. this affects the later judgment.if (dp[total_cost] ! = INF).
    Therefore, either the array element type is explicitly declareduint32_t, or initialize variables in the same wayINFFor examplememset(&INF, 0x3f, sizeof(INF))
  2. Two variables with the same name appearedtotal_kind, local variables such as
- int total_kind;
 scanf("%d", &total_kind);

The following is the C language implementation (with some code modifications)

#include <stdint.h>
 #include <stdio.h>
 #include <string.h>
 
 int min(int a, int b) { return a >= b ?   b : a;  }
 
 const uint32_t maxn = 11111, INF = 0x3f3f3f3f;
 uint32_t dp[maxn];
 int total_cost, total_kind;
 struct Obj {
 uint32_t value, cost;
 };
 
 struct Obj arr[maxn];
 
 void complete_pack()
 {
 memset(dp, 0x3f, sizeof(dp));
 dp[0] = 0;
 for (int i = 1;   i <= total_kind;  i++)
 for (uint32_t j = arr[i].cost;   j <= total_cost;  j++)
 dp[j] = min(dp[j], dp[j - arr[i].cost] + arr[i].value);
 if (dp[total_cost] !  = INF)
 printf("The minimum amount of money in the piggy-bank is %d.\n",
 dp[total_cost]);
 else
 printf("This is impossible.\n");
 }
 
 int main()
 {
 freopen("in.txt", "r", stdin);
 int T;
 scanf("%d", &T);
 while (T--) {
 int E, F;
 scanf("%d%d", &E, &F);
 total_cost = F - E;
 scanf("%d", &total_kind);
 for (int i = 1;   i <= total_kind;  i++)
 scanf("%d%d", &arr[i].value, &arr[i].cost);
 complete_pack();
 }
 return 0;
 }