01 가방 유형 문제 의 두 가지 해법

여기 서 두 문제 (유형 은 모두 01 가방 유형) 를 말 하 는데 두 문 제 는 모두 역 추적 법 과 동태 계획 두 가지 해결 방법 을 사 용 했 고 한 후에 도 시사 점 이 있 었 다.첫 번 째 문 제 는 유명한 01 가방 문제 다.01 백 팩 은 M 개 아 이 템 에서 몇 개 를 꺼 내 공간 W 인 백 팩 에 넣 는 것 으로, 각 아 이 템 의 부 피 는 W1, W2... Wn 이 며 이에 대응 하 는 가 치 는 P1, P2... Pn 이다.가방 에 넣 을 수 있 는 최대 가 치 를 구하 세 요.역 추적 법의 해법:

//0-1    ，  n 8（   8   ），M=110（        110），   w={1,11,21,23,33,43,45,55}，  p={11,21,31,33,43,53,55,65},          
#define maxsize 9
#include 
using namespace std;

int n=8;
int M=110;   //        110
int bestp=0;    //     
int noww=0;    //    
double nowp=0;     //    ，      
int x[maxsize]={0};      //          
int bestx[maxsize]={0};      //              
int w[maxsize]={0,1,11,21,23,33,43,45,55}; //    ，0     
int p[maxsize]={0,11,21,31,33,43,53,55,65};  //  ，0     


int Check(int noww,int k,int nowp) 
{
    int flag=0;    
    for (int i=k+1;i<=n;i++)
    {
        if (noww+w[i]//         
        {
            noww=noww+w[i];
            nowp=nowp+p[i];
        }
        else
        {
            flag=1;         //flag=1          
            break;
        }
    }
    if (flag==1)   //           
    {
        nowp=nowp+(p[i]/w[i])*(M-noww);     //          
    }
    return nowp;
}

void Backtrack(int noww,int k,int nowp)  //noww      ，k   （     ），nowp      
{
    if (k>n)  //               
    {
        if (nowp>bestp||bestp==0)    //1.              ，        。2.          
        {
            bestp=nowp;
            for(int i=1;i<=n;i++)
            {
                bestx[i]=x[i];
            }
        }
        return;    //            
    }
    if(noww+w[k]<=M)  //            M，      ，       ，       
    {
        x[k]=1;
        Backtrack(noww+w[k],k+1,nowp+p[k]);
    }
    if (Check(noww,k,nowp)>=bestp)  //     ，       ，        （    ，     ，          ），              ，        
    {
        x[k]=0;
        Backtrack(noww,k+1,nowp);
    }
}

int main()
{   

    cout<<"0-1    ，  n 8（   8   ），M=110（        110），   w={1,11,21,23,33,43,45,55}，  p={11,21,31,33,43,53,55,65},          。"<0,1,0);
    cout<<"    ：    ";
    for (int i=1;i<=n;i++)
    {
        if (x[i]==1)
        {
            cout<",";
        }
    }
    cout<<"    "<"   。"<return 0;
}

동적 계획 의 해법:

//0-1    
#include 
using namespace std;

int n=4;
int C=11;
int V[4+1][11+1];
int p[4+1]={0,3,4,5,7};
int w[4+1]={0,2,3,5,6};

int X[11+1];

int Knapsack()
{
    for (int i = 0; i <= C; ++i)
    {
        X[i] = 0;
    }
    for (int j = 1; j <= n; ++j)
    {
        for (int i = C; i >= 1; --i)
        {
            if (i >= w[j] && X[i - w[j]] + p[j] > X[i])
            {
                X[i] = X[i - w[j]] + p[j];
            }
        }
    }
    return X[C];
}

int main()
{   
    int bestp=Knapsack();
    cout<<"     "<"   。"<return 0;
}

두 번 째 문 제 는 작년 여름 방학 에 만 든 것 이다.절 대 는 07 년 에 대학원 시험 재 개 문제 의 최대 결산 액 이다.제목 은 다음 과 같다. 현재 경 비 는 일정 금액 의 영수증 을 청구 할 수 있다.청구 가 허 용 된 영수증 유형 은 도서 구입 (A 종), 문구 (B 종), 출장 (C 종) 을 포함 하 며, 영수증 한 장 당 총액 이 1 천원 을 초과 해 서 는 안 되 며, 영수증 한 장 당 단일 물품 의 가 치 는 600 원 을 초과 해 서 는 안 된다.지금 프로그램 을 작성 하여 제 시 된 영수증 더미 에서 청구 할 수 있 는, 주어진 금액 을 초과 하지 않 는 최대 청구 액 을 찾 아 보 세 요.입력: 테스트 입력 은 몇 가지 테스트 용례 를 포함 합 니 다.각 테스트 용례 의 첫 번 째 줄 은 두 개의 정수 Q 와 N 을 포함 하 는데 그 중에서 Q 는 주어진 결산 한도 이 고 N (N < = 30) 은 영수증 장수 이다.다음은 N 줄 입력 입 니 다. 각 줄 의 형식 은 m Type 입 니 다.1:price_1 Type_2:price_2 … Type_m:price_m 중 정수 m 는 이 영수증 에 열 린 물품 의 개수 입 니 다. Typei 와 pricei 는 제 i 항 물품 의 종류 와 가치 이다.물품 종 류 는 대문자 로 표시 한다.N 이 0 일 때 모든 입력 이 끝나 고 해당 결 과 는 출력 하지 마 십시오.출력: 모든 테스트 용례 에 1 줄 을 출력 하면 결산 할 수 있 는 최대 액 수 를 소수점 뒤의 2 자리 까지 정확하게 출력 합 니 다.샘플 입력: 200.003 2 A: 23.50 B: 100.001 C: 650.00 3 A: 59.99 A: 120.000 X: 10.00 1200.00 2 B: 600.00 A: 400.00 1 C: 200.50 1200.50 3 B: 600.00 A: 400.00 1 C: 200.00 100.00 0 0 1 A: 100.00 100.000 0 샘플 출력: 123.50 1000.00 1200.50당시 에 이 문 제 를 만 났 을 때 첫 번 째 생각 은 바로 역 추적 법 으로 다음 과 같은 절 차 를 썼 다.

#include 
#include 
#include 
#include 
#include 
using namespace std;

typedef struct Unit
{
    double A;
    double B;
    double C;
    double sum;
}Unit;

vector  ve;
double maxsum, Q;

void dfs(int k, double sum)
{
    if (k >= ve.size())
    {
        if (sum>maxsum)
        {
            maxsum = sum;
        }
    }
    else
    {
        dfs(k + 1, sum);
        if (sum + ve[k].sum <= Q)
        {
            dfs(k + 1, sum + ve[k].sum);
        }
    }
}

int main()
{
    int i, N, j, num, flag;
    double ctmp;
    string temp, subtmp;
    Unit utmp;
    while (cin >> Q >> N, N != 0)
    {
        ve.clear();
        for (i = 0; i0;
            utmp.A = 0;
            utmp.B = 0;
            utmp.C = 0;
            utmp.sum = 0;
            cin >> num;
            for (j = 0; jcin >> temp;
                if (temp[0] == 'A')
                {
                    subtmp = temp.substr(2);
                    ctmp = atof(subtmp.data());
                    if (ctmp <= 600)
                    {
                        utmp.A += ctmp;
                        utmp.sum += ctmp;
                    }
                    else
                    {
                        flag = 1;
                        break;
                    }
                }
                else if (temp[0] == 'B')
                {
                    subtmp = temp.substr(2);
                    ctmp = atof(subtmp.data());
                    if (ctmp <= 600)
                    {
                        utmp.B += ctmp;
                        utmp.sum += ctmp;
                    }
                    else
                    {
                        flag = 1;
                        break;
                    }
                }
                else if (temp[0] == 'C')
                {
                    subtmp = temp.substr(2);
                    ctmp = atof(subtmp.data());
                    if (ctmp <= 600)
                    {
                        utmp.C += ctmp;
                        utmp.sum += ctmp;
                    }
                    else
                    {
                        flag = 1;
                        break;
                    }
                }
                else
                {
                    flag = 1;
                    break;
                }
            }
            if (flag == 0 && utmp.sum <= 1000 && utmp.sum <= Q)
            {
                ve.push_back(utmp);
            }
        }
        maxsum = 0;
        dfs(0, 0);
        cout.setf(ios::fixed);
        cout.precision(2);
        cout << maxsum << endl;
    }
    system("pause");
    return 0;
}

그러나 제출 할 때 시간 이 초과 되 었 다 는 것 을 발견 하 니 역 추적 법 이 너무 느 린 것 같다.나중에 인터넷 에서 답 을 찾 았 을 때 이 문제 의 동적 기획 해법 을 발 견 했 는데 다른 사람의 코드 이기 때문에 나 는 여기에 붙 이지 않 았 다.인터넷 주소http://blog.csdn.net/xiexingshishu/article/details/8799669。 당시 젊 었 기 때문에 (사실은 멍청 하 다) 이것 이 바로 01 가방 문제 라 는 것 을 발견 하지 못 했다. 만약 에 거 슬러 올 라 가 는 시간 이 너무 길 면 동태 적 인 계획 으로 시간 을 줄 일 수 있다.