銅貨

区分アルゴリズムぶんかつアルゴリズム:ダイナミックプログラミングダイナミックプログラミング

質問する

n種類のコインがあります.コイン1枚あたりの価値は違います.このコインを適当に使って、価値の和をk元にしたいです.その場合の数を求める.コイン1枚につきいくつか使えます.
使用するコインの構成は同じですが、順番が違うのは同じ場合です.
入力
最初の行はn,kを与える.(1≦n≦100,1≦k≦10000)次のn行は、各硬貨に価値を与える.硬貨の価値は100000以下の自然数である.
しゅつりょく
1行目の出力状況の数.例数は231未満である.
入力例1
3 10
1
2
5
サンプル出力1
10

問題を解く

まず,前のインデックスで計算した結果を,後のインデックスにおいてベンチマークアップ方式で利用すべきであると考え,DPでアクセスした.
しかし、最初は、dp[3]=(dp[0]dp[3]+(dp[1]dp[2])のように、kを作成する場合は、kの数を検索し、それらの間の積で点火式を実現することができ、例に適用されるが、一致しない.上の点火式の間違いは以下の通りです.
n=2,k=4/硬貨値:1,2
上記の条件では、dp[0]=1、dp[1]=1、dp[2]=2、dp[3]=2となり、dp[2]の値自体が上記の点化式で正しく更新されていない.また、dp[4]を求める過程から分かるように、硬貨価値が1の硬貨だけで4を作る場合、数は繰り返し増加し、dp[4]の値は本来出るべき結果よりも大きな値になる.
もし私が「X元」を使って特定の金額を創造する過程であれば、少なくともその金額はX元以上であるべきだ.例えば、3元硬貨である金額を作る場合、1元または2元は作れません.これを考慮して点火式を再作成すると、dp[Y]=dp[Y]-dp[Y-X]となる.つまり、X元を活用してY元を作るためには、Y-X元を作るときに数を加えればいいのです.これを実装プロセスに適用すると、二重複文が使用され、最初の複文の変数は配列のインデックスを指定し、2番目の複文の変数は生成されたコインの価値を探すために使用されます.(つまり、Yを使います.)
時間の複雑さを簡単に考えれば、O(NK)ですが、2番目の複文の起点は0ではなく、そのインデックスのコインの価値であり、実際の時間の複雑さはO(NK)より小さくなります.

ソースコード

#include <bits/stdc++.h>

using namespace std;

int n, k;
vector<int> v(101);
int dp[10001];
void solve();

int main() {
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	
	cin >> n >> k;
	for(int i = 1; i < n + 1; i++) {
		cin >> v[i];
	}
	
	solve();
	
	return 0;
}

void solve() {	
	dp[0] = 1;
	if(v[0] > k) {
		cout << 0 << endl;
	}
	else {
		for(int i = 1; i < n + 1; i++) {
			for(int j = v[i]; j < k + 1; j++) {
				dp[j] = dp[j] + dp[j - v[i]];
			}
		}
	}
	
	cout << dp[k] << endl;
}

題出所:https://www.acmicpc.net/problem/22932

カイドウ草が白駿で「そうだ!!」判定を受けた