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

-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; }