카테고리 없음
[java] 반복되는 숫자없이 주어진 합계를 얻기 위해 가능한 모든 조합을 가져옵니다.
필살기쓰세요
2021. 2. 28. 12:22
Java : 조합을 나열해야하는 경우 :
static void sumToValue(int limit, int sum, int count, List<Integer> resultIP) {
if (limit >= 0 && sum == 0 && count == 0) {
// print resultIP, because it is one of the answers.
System.out.println("sum(" + Arrays.toString(resultIP.toArray()) + ")");
} else if (limit <= 0 || count == 0 || sum <= 0) {
// not what we want
return;
} else {
// Two options: choose current limit number or not
sumToValue(limit - 1, sum, count, resultIP);// Not choose the limit
// number
// or choose the limit number
List<Integer> resultNext = new ArrayList<Integer>(resultIP);// copy
// resultIP
resultNext.add(limit);
sumToValue(limit - 1, sum - limit, count - 1, resultNext);
}
}
카운트 만 필요한 경우 :
static void sumToValueCount(int limit, int sum, int count) {
int dp[][][] = new int[limit + 1][sum + 1][count + 1];
for (int i = 0; i <= limit; i++) {
for (int j = 0; j <= sum; j++) {
for (int k = 0; k <= count; k++) {
if (j == 0 && k == 0) {
dp[i][j][k] = 1;
} else if (i == 0 || j <= 0 || k == 0) {
dp[i][j][k] = 0;
} else {
// check to prevent negative index
if (j - i >= 0) {
// two options: choose the number or not choose the number
dp[i][j][k] = dp[i - 1][j - i][k - 1] + dp[i - 1][j][k];
} else {
dp[i][j][k] = dp[i - 1][j][k];
}
}
}
}
}
System.out.println(dp[limit][sum][count]);
}
다음과 같은 주요 함수 호출에서 :
//limit is 45, sum is the sum we want, count is 6 referring to the question.
sumToValue(45, 255, 6, new ArrayList<Integer>());
sumToValueCount(45, 255, 6);
동적 프로그래밍을 사용하여이 문제를 해결할 수 있습니다.
그림 dp[N][LastNumber][ElementCount]산출하기 위해 얼마나 많은 방법이다 N마지막 번호입니다 LastNumber및 요소의 수입니다 ElementCount. 와 N = 1..255, LastNumber = 1..45,ElementCount = 1..6
dp[N][LastNumber][ElementCount]서브 솔루션에서
얻을 수 있습니다 dp[N-LastNumber][1][ElementCount-1]+ dp[N-LastNumber][2][ElementCount-1]... +dp[N-LastNumber][LastNumber-1][ElementCount-1]
베이스 케이스이다 dp[i][i][1] = 1위한i = 1..45
이 요약하는 방법을 여러 가지 방법으로 질문하는 경우 M는 asnwer입니다 dp[M][i][6]위해i = 1..45
다음은 동적 프로그래밍을 사용하여 C ++에서 작성한 코드입니다. n추가 할 최대 수입니다. m요소 수이며 s목표 합계입니다.
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
int mini(int n, int m) {
return m * (m + 1) / 2;
}
int maxi(int n, int m) {
return m * (2 * n - m + 1) / 2;
}
typedef std::vector<unsigned long long> Long1D;
typedef std::vector<Long1D> Long2D;
typedef std::vector<Long2D> Long3D;
int main(int argc, const char * argv[]) {
int n, m, s;
n = 45;
m = 6;
s = 21;
if ((s < mini(n, m)) || (s > maxi(n, m))) {
cout << 0 << endl;
return 0;
}
Long3D dp(2, Long2D(m + 1, Long1D(s + 1)));
for (int i = 1; i <= n; ++i) {
for (int j = 1; j <= min(i, m); ++j) {
for (int k = 1; k <= s; ++k) {
if ((k < mini(i, j)) || (k > maxi(i, j))) {
dp[i % 2][j][k] = 0;
}
else if ((k == mini(i, j)) || (k == maxi(i, j)) || j == 1) {
dp[i % 2][j][k] = 1;
}
else {
dp[i % 2][j][k] = 0;
// !IMPORTANT -- general situation: dp[i][j][k]=dp[i-1][j-1][k-j]+dp[i-1][j][k-j]
if (k - j > mini(i - 1, j - 1))
dp[i % 2][j][k] += dp[(i - 1) % 2][j - 1][k - j];
if (k - j < maxi(i - 1, j))
dp[i % 2][j][k] += dp[(i - 1) % 2][j][k - j];
}
}
}
}
cout << dp[n % 2][m][s] << endl;
return 0;
}
출처
https://stackoverflow.com/questions/39969978