計(jì)算機(jī)算法設(shè)計(jì)與分析（第三版）P78
背包問題：
m(i,j) = (1). max{m[i+1][j],m[i+1][j-w[i]]+v[i]}
           (2).m[i+1][j]

m(n,j) = (1) v[n] j>=w[n]
            (2) 0 0<=j<w[n]

m[i][j]：表示背包容量為j，可選擇的物品為i,i+1,....,n是0-1背包問題的最優(yōu)值。


#include<iostream>
#include<time.h>
#include<stdlib.h>
using namespace std;

#define N 5
#define C 25

int m[N+1][C+1];

//#define MAX(a,b)  ((a)>(b)?(a):(b))

int Min(int a,int b)
{
        return a<b?a:b;
}

int Max(int a,int b)
{
        return a>b?a:b;
}

void print(int *x)
{
        for(int i=1;i<=N;i++)
        {
              cout<<x[i]<<"\t";
        }
        cout<<endl;
}

void fb(int *w)
{
       cout<<"\n";
       
        int x[N+1];
        int c=C;
        
        for(int i=0;i<=N;i++)
        {
                x[i]=-1;
        }
        
        for(int i=1;i<N;i++)
        {
                if(m[i][c]==m[i+1][c]){
                        x[i]=0;
                }
                else{
                        x[i]=1;
                        c-=w[i];
                        cout<<w[i]<<"\t";
                }
        }
        
        cout<<endl;
        
        x[N] = (m[N][c])?1:0;
        print(x);
}


void f(int *w,int *v)
{        
        int max = Min(w[N]-1,C);
        //int max = min(w[N],C);
        for(int i=0;i<=N;i++)
        {
                for(int j=0;j<=C;j++)
                {
                        m[i][j]=-1;
                }
        }
        
        
        
        for(int j=0;j<max;j++)
        {
                m[N][j] = 0;
        }
        
        for(int j=max;j<=C;j++)
        {
                m[N][j] = v[N];
        }
        
        for(int i=N-1;i>1;i--)
        {
                max = Min(C,w[i]-1);
                //max = min(C,w[i]);
                for(int j=0;j<max;j++)
                {
                        m[i][j]=m[i+1][j];
                }
                
                for(int j=w[i];j<=C;j++)
                {
                        m[i][j] = Max(m[i+1][j],m[i+1][j-w[i]]+v[i]);
                }
        }
        
        m[1][C] = m[2][C];
        if(C>=w[1]){
                m[1][C] = Max(m[1][C],m[2][C-w[1]]+v[1]);
        }
        
        //print(m);
        
        for(int i=1;i<=N;i++)
        {
                for(int j=1;j<=C;j++)
                {
                        cout<<m[i][j]<<" ";
                }
                cout<<endl;
        }
        
        
        fb(w);
        
             
}

int main()
{
        int i;
        int w[N],v[N];
        
        srand(time(NULL));
        for(i=1;i<=N;i++)
        {
                w[i]=rand()%10;
                v[i]=rand()%25;
        }
        
        f(w,v);
        
        return 0;
}