가방 문제. - 조합 문제. - 배열 문제.
1166 단어 알고리즘
(이 는 완전 가방 문제 로 이해 하기 쉬 운 회 삭 재 귀 법 을 사용한다. 같은 종류의 문 제 는 잔돈 을 찾 는 것 이다.)
이 문 제 는 조합: 1 부터 n - 1 까지 의 수 구 조합 과 n 인 식 이 가장 먼저 떠 올 랐 다.하지만 각 숫자의 개 수 는 여러 개 일 수 있 고 제한 이 있어 완전 가방 과 같다.
조합 문제 와 가방 문제 의 관계:
1. 중복 요소 의 집합 이 없 는 조합 - 01 가방: 검색 지점 마다 (요소 마다) 숫자 유 무 만 을 고려 합 니 다.
2. 중복 요소 의 집합 조합 - 완전 가방: 모든 검색 점 (모든 요소) 에서 숫자의 개 수 를 고려 합 니 다.
반복 되 는 숫자 배열 문제 가 생각 났 다.
물음: 1231428 의 전체 배열 을 구하 세 요.
첫 번 째 단 계 를 예 로 들 면 1 과 뒤의 모든 숫자 를 교환 하여 뒤쪽 문자열 의 배열 문제 에 들어간다.하지만 같은 숫자 와 는 바 꿀 수 없다.
#include
#include
using namespace std;
// n, n 。
void step(int index,int currentsum,int* result,int length,int sum)
{
if(currentsum==0)
{
cout<0)
cout<=sum)
return;
int n=0;
while((n*index)<=currentsum)
{
result[index-1]=n;
step(index+1,currentsum-n*index,result,length,sum);
result[index-1]=0;
n++;
}
}
void AllSum(int n)
{
if(n<=1)
exit(1);
int* result=new int[n-1];
step(1,n,result,n-1,n);
delete[] result;
}
int main(){
int n;
cout<>n;
AllSum(n);
return 0;
}
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
【Codility Lesson3】FrogJmpA small frog wants to get to the other side of the road. The frog is currently located at position X and wants to get to...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.