Home>

I want to confirm the mistake in the code that I thought about "Atcodr Beginner Contest 015 D Takahashi-kun's suffering"

Test case 36/47 is correct and 11 questions are incorrect.

Corresponding source code
W = int (input ())
N, K = map (int, input (). split ())
ab = [list (map (int, input (). split ())) for _ in range (N)]
dp = [[0] * (W + 1) for _ in range (N + 1)]
cnt = [[0] * (W + 1) for _ in range (N + 1)]
for i in range (N):
    a, b = ab [i]
    for j in range (W + 1):
        if j-a<0:
            dp [i + 1] [j] = dp [i] [j]
            cnt [i + 1] [j] = cnt [i] [j]
        else: else:
            if dp [i] [j]<dp [i] [j-a] + b:
                cnt [i + 1] [j] = cnt [i] [j-a] +1
                dp [i + 1] [j] = dp [i] [j-a] + b
            else: else:
                cnt [i + 1] [j] = cnt [i] [j]
                dp [i + 1] [j] = dp [i] [j]
ans = 0
for i in range (W + 1):
    if cnt [N] [i]<= K:
        ans = dp [N] [i]
print (ans)
What I tried

I've been learning dynamic programming recently, and I wondered if I could use the 2D DP table that often appears. Since there are many variables for constraints, I think that one 2D DP table is not enough, so I created a DP table with a variable name of cnt and counted the number of screenshots separately from the main DP table (variable name: dp). I wondered if it would work. The sample case passed without any problem, and the table seemed to be updated well, so I thought it would be a good idea, but it turned out to be test case WA. Is the idea wrong? Thank you.

  • Answer # 1

    If the number of sheets exceeds K, it cannot be used no matter how important the total is
    In the current code, if the width is the same and the importance is high, it is updated without looking at the number of sheets at all, but with that, there are combinations that can not be used beyond K, and there are many sheets and it is not possible to increase the importance later, so the future potential Combinations without are likely to remain in the table.

    Here's an example that doesn't work. try it.

    2
    3 1
    twenty three
    1 2
    1 2