元々のコードにバグがあるように見えます。
たとえば、3種類のコインを使用して合計で18にしたい場合、質問に書いてもらったコードでは以下の入力では'Yes'になります。
3 18
1 3
2 3
5 6
しかし、以下の入力では'No'になります。18 = 5x3 + 1x3 なので、明らかにコードに問題があります。
3 18
2 3
5 6
1 3
1Like
atcoder とアルゴ式 （動的計画法）同じ問題のようで正解にならない
下記の２問の違いが分からない
上記の2問について、アルゴ式にて以下のコードを提出し、正答しました
N,M = map(int,input().split())
A,B = [None]*(N+1),[None]*(N+1)
for i in range(1,N+1):
A[i],B[i] = map(int,input().split())
INF = 10**7
dp = [[INF]*(M+1)for _ in range(N+1)]
dp[0][0]=0
for i in range(1,N+1):
for j in range(M+1):
if dp[i-1][j]!=INF:
dp[i][j]=0
if j>=A[i]:
if dp[i][j-A[i]]<B[i]:
dp[i][j]=dp[i][j-A[i]]+1
print("Yes"if dp[-1][-1]!=INF else "No")
そしてatcoderで Money in Handという同じような問題に出くわし、このコードを提出しましたが、1/3ほどのテストケースが通りませんでした。
これらの２問、何が違うのでしょうか？なぜatcoderでは通らないのかがさっぱりわかりません。
0
4Answer
@kichirb3さんも仰っている通り、現状のコードだと不正な判定となるパターンがあります。
以下のような単純な例でもNoが返ってきます。
2 8
3 2
2 3
判定が不正になる原因ですが、例えば上記入力でi=2, j=6の時、以下のような更新が走ってしまいます。
6の箇所が3となっており、8の箇所がOKとなるパターンが見つからなくなってしまっています。
以下のような修正をすることで、ACとなることが確認できました。
N,M = map(int,input().split())
A,B = [None]*(N+1),[None]*(N+1)
for i in range(1,N+1):
A[i],B[i] = map(int,input().split())
INF = 10**7
dp = [[INF]*(M+1)for _ in range(N+1)]
dp[0][0]=0
for i in range(1,N+1):
for j in range(M+1):
if dp[i-1][j]!=INF:
dp[i][j]=0
- if j>=A[i]:
+ elif j>=A[i]:
if dp[i][j-A[i]]<B[i]:
dp[i][j]=dp[i][j-A[i]]+1
print("Yes"if dp[-1][-1]!=INF else "No")
1Like
完全に理解しました。僕のコードは選ぶ場合と選ばない場合どちらもif文にしているという間違いを犯していました....
お二人の方、お力添え本当に感謝します。
0Like
あ、これコンテストある日にアルゴ式でちょうど解いてたから一瞬で気づいたやつ…
0Like