가방 문제. - 조합 문제. - 배열 문제.

1166 단어 알고리즘
문제: 출력 과 n 의 모든 화식, 중복 식 이 있어 서 는 안 됩 니 다.
 (이 는 완전 가방 문제 로 이해 하기 쉬 운 회 삭 재 귀 법 을 사용한다. 같은 종류의 문 제 는 잔돈 을 찾 는 것 이다.)
이 문 제 는 조합: 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;
}

좋은 웹페이지 즐겨찾기