악 록 산 에서 물 긷 기

[문제 설명]
시장 에는 p 종 통 (각 종 무한 다) 이 있 고 용적 은 각각 v [1], v [2],..., v [p] 이다.만약 통 을 좀 사려 면 q 리터 의 물 을 낼 수 있 습 니 다. 적어도 몇 개의 통 을 사 야 하고 어떤 용적 의 통 을 사 야 하 는 지 계산 해 보 세 요.만약 수량 이 가장 적은 방안 이 여러 가지 가 있다 면, 너 는 가장 작은 통 의 용적 을 최대한 작은 방안 을 선택해 야 한다.여러 가지 방안 이 있다 면 두 번 째 작은 통 의 용적 을 최대한 작은 방안 을 선택해 야 한다.예 를 들 어 용적 이 {3, 5, 7, 9} 인 네 개의 통 을 구 매 하 는 것 이 {3, 6, 7, 8} 인 것 보다 낫다.
[형식 입력]
첫 번 째 줄 은 정수 q 를 포함 하여 물 을 채취 하 는 용적 을 표시 합 니 다.두 번 째 줄 은 하나의 정수 p 를 포함 하여 시장 에서 배럴 의 종 수 를 나타 낸다.다음 p 줄, 각 줄 의 수 는 각 통 의 용적 v [1], v [2],..., v [p] 순 으로 나 뉜 다.
[출력 형식]
출력 1 줄, 두 개의 수 간 을 빈 칸 으로 구분 하고, 첫 번 째 수 k 는 가장 적은 통 의 수량 이 며, 다음 k 개 수 는 작은 것 에서 큰 것 으로 각 통 의 용량 을 출력 합 니 다.
[샘플 입력]
16 3 3 5 7
[출력 사례]
2 3 5
【 데이터 범위 】
q<=20000 p<=100
전송 소 p2991 악 록 산 에서 물 긷 기
【DFS】
[문제 분석] 처음에는 복잡 하 게 생각 했 는데 물 을 붓 는 문 제 를 연상 시 키 고 선택 할 용적 을 검색 한 후에 검색 을 통 해 선택 할 수 있 는 용적 으로 목표 수량 을 판단 하려 고 했다.그러나 생각 만 해도 복잡 해서 버 렸 다.달 라 오 에 게 물 어 보 니 탁 트 였 다.원래 이 문제 에서 용적 이 vi 인 통 을 선택 한 후에 몇 번 사용 할 수 있 기 때문에 문 제 는 큰 통 M 이 있다 고 가정 하고 n1 개의 v1 통, n2 개의 v2 통 을 사용 하 는 것 이다.............................................(샘플 즉 2 * 3 + 2 * 5 = = 8) 문 제 는 두 가지 ① 종류 가 가장 적다.② 같은 종류 에서 용적 이 가장 적 고 가능 한 한 작 으 며 선택 한 종 수 를 알 수 없 기 때문에 당연히 교체 가 깊 어 집 니 다 ~ 부분 집합 이 생 성 되 는 맛 이 있 습 니 다. or 를 선택 하지 않 습 니 다 ~ 따라서 의사 코드 를 쓸 수 있 습 니 다.

bool dfs(int t,int rest,int s)
{
    if(s==k)
    {
        if(rest==0)
         {
            if(better())  ans;
            return 1
         }
         return 0;
    }
    for(int i=0;i*v[t]<=rest;i++)//i*v[t]         
    {
        if(i==0)//       
        {
          ..... a[z]=v[i];
        }
        else// i      
        {   
          .... 
        }
    }
}
for(k=1;;k++)
if(dfs(1,q,0))break;
printf("%d",k);
for(int i=0;iprintf(" %d",ans[i]);

[디 테 일 처리]

bool ok 의 설정 도 리 는 이집트 점수 와 마찬가지 로 우 리 는 해 를 찾 으 면 되 는 것 이 아니 라 k 종의 용적 통 아래 에 있 는 모든 해 를 검색 하고 요구 에 따라 최 적 화 를 찾 아야 한다.

better () 함수 의 작성 은 '수량 이 가장 적은 방안 이 여러 가지 가 있 으 면 가장 작은 통 의 용적 이 가능 한 한 작은 방안 을 선택해 야 한다. 만약 에 여러 가지 방안 이 있다 면 두 번 째 작은 통 의 용적 이 가능 한 한 작은 방안 을 선택해 야 한다' 는 뜻 이다. 따라서 어 릴 때 부터 a [] 와 ans [] 를 옮 겨 다 니 며 a [i] ＜ ans [i] 를 발견 하면 return 1 이 고 a [i] > ans [i] 를 발견 하면 return 1 이다.검색 하기 전에 오름차 순 으로 정렬 해 야 합 니 다!

예비 처 리 는 ans [] 를 모두 무한대 로 바 꾸 어 1 조 의 입력

에 편리 하도록 해 야 한다.

가지치기
if(t>n)return false;//최대 치 초과 고려 - > 무의미 한 검색 피하 기
【CODE】

#include
#include
#include
#include
#include
#include
#include
#define inf 2147483647
using namespace std;
int x,n,v[105],k,cnt=1;
int a[20002],ans[20002];//       

bool better()
{
    for(int i=1;i<=k;i++)
    if(a[i]return 1;
    else if(a[i]>ans[i])return 0;
    return 0;
}


bool dfs(int t,int rest,int s)//   t    ， t-1   rest ， t-1       
{
    if(s==k)
    {
      if(rest==0)//   x 
      {
        if(better())
         for(int i=1;i<=k;i++)ans[i]=a[i];
        return true; 
      } 
      return false;     
    }

    if(t>n)return false;//         ——>         

    bool ok=0;

    for(int i=0;v[t]*i<=rest;i++)//   i        
    {
        if(i!=0)//      
        {
         int V=v[t]*i;
         a[s]=v[t];
         //cnt+=1;
         if(dfs(t+1,rest-V,s+1))ok=1;
         //cnt-=1;
        }
        else 
        if(dfs(t+1,rest,s))ok=1;
    }
    return ok;
} 

int main()
{
//  freopen("in.txt","r",stdin);
    for(int i=1;i<=104;i++)ans[i]=99999;//    
    scanf("%d%d",&x,&n);
    for(int i=1;i<=n;i++)
    scanf("%d",&v[i]);

    sort(v+1,v+1+n);//    ,①  dfs        ->       
                    //         ②              ，    
    for(k=1;;k++)// k     -->dfs      ！！ 
    if(dfs(1,x,0))break; 

    printf("%d",k);
    for(int i=0;iprintf(" %d",ans[i]);

    return 0;
}

【DP+DFS】
인터넷 상에 서 대신 이 에너지 가 목표 수량 을 취 할 지 판단 할 때 사용 하 는 것 은 DP 의 사상 (완전 가방) But... dp 는 아직 배우 지 않 았 습 니 다. 나중에 dp + dfs 방법 을 보충 하 겠 습 니 다.
Written By Mr.Shadow from CQYZ

악 록 산 에서 물 긷 기

좋은 웹페이지 즐겨찾기