AtcoderのB問題をdpで解きたいです。

Question

https://atcoder.jp/contests/abc087/tasks/abc087_b
この問題をdpで解こうとしています。

#include <bits/stdc++.h>
using namespace std;

const int INF = 1<<29;

int main(){
	int B[3];
    for(int i=0;i<3;i++) cin >> B[i];
    int X; cin >> X;
	int dp[6][21000];
	int A[3] = {500 , 100 ,50};
	for (int i = 0; i < 6; ++i) for (int j = 0; j < 21000; ++j) dp[i][j] = INF;
	dp[0][0] = 0; // dp[0][0] だけ 0 に

    int count = 0 ;

	for (int i = 0; i < 3; ++i) {
    	for (int j = 0; j <= X; ++j) {
      		if (dp[i][j] < INF) dp[i+1][j] = 0;
      		if (j >= A[i]) {
        		if (dp[i][j-A[i]] < INF) {
            	dp[i+1][j] = min(dp[i+1][j], 1);
        	}
        	if (dp[i+1][j-A[i]] < B[i]) {
            	dp[i+1][j] = min(dp[i+1][j], dp[i+1][j-A[i]] + 1); 
        		}
      		}
			if(dp[3][X] < INF){
				count++;
				dp[3][X] = INF;
			}
    	}
  	}

	cout << count << endl;
}

基本的な考え方は　https://algo-method.com/tasks/313
を参考にしています。これだと答えが思い通りに出ないのですが、どなたかご教示いただけないでしょうか？
例えば、入力で
5
1
0
150
となっているとき、このようなパターンは存在しないので0のはずが、1を出力してしまいます。
他にも
30
40
50
6000
で213パターンあるのに、1しか出力しないなどです

Comments

[y_waiwai]

どういう答えが出るんでしょうか
そして、それがどうなればいいんでしょう。
具体的に説明しましょう

Answer 1

int dp[6][21000]; の 6 と 21000 はどういう意味ですか？
dp[i][j] の i は 0～3 しか使っていないようですね。
for (int j = 0; j <= X; ++j) { ですが、X は 50 の倍数なのに、
j を 1ずつ増やすのは無駄ではないのですか？

私だったら次のようなコードを書きます。

#include <iostream>
using namespace std;

int count;

void step(int num[], int i, int x)
{
 	static int coin[3] = { 500, 100, 50 };
	if (x == 0) count++;
	else if (x > 0 && i < 3) 
		for (int j = min(num[i], x / coin[i]); j >= 0; j--)
			step(num, i+1, x - coin[i]*j);
}

int main()
{
	int num[3], x;
	for (int i= 0; i < 3; i++) cin >> num[i];
	cin >> x;
	step(num, 0, x);
	cout << count << endl;
}

Answer 2

結論から言うと、「基本的な考え方」のリンク先の方法そのままで解くのは無理です。

リンク先の問題はパターン数が必要ないので、途中段階で複数のパターンがあった場合、minを使って最も数値の個数が少ないパターン１つのみを残す作りになっています。
そのために、いくらパターンがあっても出力は1になります。

あとは、前提条件が異なります。
リンク先の問題は各数字が1つ以上存在する前提ですが、AtCoderの問題は0の場合があります。
5,1,0,150という入力で1が出力されるのは、こちらが原因です。