程序代码：

#define CAP 17

vector<int> items = {3, 4, 7, 8, 9};
vector<int> values = {4, 5, 10, 11, 13};
vector<bool> isSelect(items.size());
vector<int> maxKnown(CAP+1);
vector<int> itemKnown(CAP+1);

int knap(int cap, int depth)
{
    int i, space, max, maxi, t;
    
    if (maxKnown[cap])
    {
        return maxKnown[cap];
    }
    
    for (i = 0, max = 0, maxi = -1; i < items.size(); i++)
    {
        if (!isSelect[i])
        {
            isSelect[i] = true;
            
            space = cap - items[i];

            if (space >= 0)
            {
                for (int j = 0; j < depth; j++)
                {
                    printf("  ");
                }
                
                printf("%d\n", space);
                
                t = knap(space, depth+1) + values[i];
                
                if (t > max)
                {
                    max = t;
                    maxi = i;
                }
            }
            
            isSelect[i] = false;
        }
    }
    
    maxKnown[cap] = max;
    itemKnown[cap] = maxi;
    
    return max;
}

int main(void)
{
     int max = knap(CAP, 0);
    
    if (max != 0)
    {
        printf("max = %d\n", max);
        int cap = CAP;
        vector<int> selected;
        
        while (itemKnown[cap] != -1 && cap - items[itemKnown[cap]] >= 0)
        {
            selected.push_back(items[itemKnown[cap]]);
            cap = cap - items[itemKnown[cap]];
        }
        
        for (int i = 0; i < selected.size(); i++)
        {
            printf("%d ", selected[i]);
        }
    }

    return 0;
}

程序代码：

#define CAP 17

vector<int> items = {9, 8, 7, 4, 3};
vector<int> values = {13, 11, 10, 5, 4};
vector<int> maxKnown(CAP+1);
vector<int> itemKnown(CAP+1);

int main(void)
{
    int i, j, space, max, maxi, t;
    
    for (i = 0; i <= CAP; i++)
    {
        for (j = 0, max = 0, maxi = -1; j < items.size() ; j++)
        {
            if ((space = i - items[j]) >= 0)
            {
                if ((t = maxKnown[space] + values[j]) > max)
                {
                    max = t;
                    maxi = j;
                }
            }
        }
        
        maxKnown[i] = max;
        itemKnown[i] = maxi;
    }
    
    if (max != 0)
    {
        printf("max = %d\n", max);
        int cap = CAP;
        vector<int> selected;
        
        while (itemKnown[cap] != -1 && cap - items[itemKnown[cap]] >= 0)
        {
            selected.push_back(items[itemKnown[cap]]);
            cap = cap - items[itemKnown[cap]];
        }
        
        for (int i = 0; i < selected.size(); i++)
        {
            printf("%d ", selected[i]);
        }
    }
    
    return 0;
}