HDU 1114 is a complete backpack. If you take out the knapsack function alone, you will WA, and if you write it into the main function, you will AC. Why?

topic description

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

meaning: little friends save money and do things by putting money in the piggy bank. Unless the piggy bank is broken, you can"t get the money out. Weigh the piggy bank in order to know if you have saved enough money. Then tell the weight and value of each coin and ask how much money there may be in the piggy bank.

sources of topics and their own ideas

regular complete knapsack problem, as shown in the title. complete_pack () will AC if you write it into main () , and you will WA if you write it alone.

related codes

/ / here complete_pack () is written separately for WA.

-sharpinclude <iostream>
-sharpinclude <cstring>
-sharpinclude <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; iPP)
        for (int j = arr[i].cost; j <= total_cost; jPP)
            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; iPP)
            scanf("%d%d", &arr[i].value, &arr[i].cost);
        complete_pack();
    }
    return 0;
}
C cPP
Jun.01,2022

two areas need to be corrected

  1. after initializing the array with memset (dp, 0x3f,...) , the element value is not necessarily 0x3f3f3f3f , depending on the number of int type digits of the compiler, only 32 bits are valid. This affects the later judgment if (DP [total _ cost]! = INF) .
    therefore, either explicitly declare the array element type as uint32_t , or initialize the variable INF , such as memset (& INF, 0x3f, sizeof (INF))
  2. there are two variables with the same name total_kind . Local variables, such as
  3. , should be deleted.
        - int total_kind;
        scanf("%d", &total_kind);

the following is the c language implementation (with a few modifications to the code)

-sharpinclude <stdint.h>
-sharpinclude <stdio.h>
-sharpinclude <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; iPP)
        for (uint32_t j = arr[i].cost; j <= total_cost; jPP)
            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; iPP)
            scanf("%d%d", &arr[i].value, &arr[i].cost);
        complete_pack();
    }
    return 0;
}
MySQL Query : SELECT * FROM `codeshelper`.`v9_news` WHERE status=99 AND catid='6' ORDER BY rand() LIMIT 5
MySQL Error : Disk full (/tmp/#sql-temptable-64f5-7bd2e2-905b.MAI); waiting for someone to free some space... (errno: 28 "No space left on device")
MySQL Errno : 1021
Message : Disk full (/tmp/#sql-temptable-64f5-7bd2e2-905b.MAI); waiting for someone to free some space... (errno: 28 "No space left on device")
Need Help?