C++回溯法0/1背包问题DKNAP

余祥宣, 崔国华, 邹海明. 计算机算法基础.3版[M]. 华中科技大学出版社, 2006.
P141 算法6.7

#include<iostream>
#include<fstream>
using namespace std;

#define MAX 25
bool back(int &_p,int &_w, int k, int F[], int W[],int P[],int w[],int p[])
{
    int label = 0;
    for (int i = F[k]; i < F[k+1]; i++)
    {
        if (W[i] == _w&&P[i]==_p)
        {
            label = 1;
            break;
        }
    }
    for (int i = F[k-1]; i < F[k]; i++)
    {
        if (W[i] == _w&&P[i] == _p)
        {
            label = 0;
            break;
        }
    }
    if (label == 1)
    {
        _p = _p - p[k];
        _w = _w - w[k];
    }
    return label;
}
void DKNAP(int p[], int w[], int n, int M, int m)
{
    int P[MAX],W[MAX],F[MAX];
    int pp, ww;
    int l, h, u, i, j, next;

    F[0] = 1;
    P[1] = W[1] =P[0]=W[0]= 0;
    l = h = 1;
    F[1] = next = 2;
    for (i = 1; i <= n; i++)
    {
        int k = l;

        u = l;
        int max = W[l] + w[i];
        for (int index = l+1; index <= h; index++)
        {
            if (W[index] + w[i] > max)
            {
                max = W[index] + w[i];
                u = index;
            }
        }

        for (j = l; j <= u; j++)
        {
            pp = P[j] + p[i];
            ww = W[j] + w[i];

            while (k <= h&&W[k] < ww)
            {
                P[next] = P[k];
                W[next] = W[k];
                next++;
                k++;
            }

            if (k <= h&&W[k] == ww)
            {
                if (P[k] > pp)
                    pp = P[k];
                k++;
            }

            if (pp > P[next - 1])
            {
                P[next] = pp;
                W[next] = ww;
                next++;
            }

            while (k <= h&&P[next-1])
            {
                k++;
            }
        }
        while (k <= h)
        {
            P[next] = P[k];
            W[next] = W[k];
            next++;
            k++;
        }
        l = h + 1;
        h = next - 1;
        F[i + 1] = next;
    }
    cout << "P ";
    for (int i=0; i < MAX; i++)
    {
        cout << i << ":" << P[i] << " ";
    }
    cout << endl << "W ";
    for (int i = 0; i < MAX; i++)
    {
        cout << i << ":" << W[i] << " ";
    }
    cout << endl << "F ";
    for (int i = 0; i <=n+1; i++)
    {
        cout <<i<<":"<< F[i]<<" ";
    }
    cout << endl;

    //回溯法
    for ( i = F[n]; i < F[n+1]; i++)
    {
        if (W[i] <= M&&W[i + 1] > M)
            break;
    }
    cout << P[i] << " " << W[i]<< endl;
    int _p = P[i], _w = W[i];
    for (j = n; j > 0; j--)
    {
        cout <<"w"<< j << "=>" << back(_p, _w, j, F, W, P, w, p)<<" ";
    }
}
int main()
{
    //int p[] = { 0,1,2,5 };
    //int w[] = { 0,2,3,4 };
    int p[] = { 0, 4, 6, 8, 10 };
    int w[] = { 0, 3, 4, 5, 6 };
    int i = 0; cout << "p:";
    while (i < 4)
        cout << p[++i] << " ";
    i = 0; cout << endl<<"w:";
    while (i < 4)
        cout << w[++i] << " ";
    cout << endl;
    DKNAP(p, w, 4, 15, 15);
    cout << endl;
    system("pause");
    return 0;
}

运行结果