計算機算法設計與分析（第三版）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;
}