0-1背包（动态规划）
问题描述：给定n种物品和一背包。物品i的重量是wi，其价值是vi，背包的容量为c。 问应如何选择装入背包的物品，使得装入背包中物品的总价值最大?
问题分析：对于一种问题，要么装入背包，要么不装。所以对于一种物品的装入状态可以取0和1。
eg:物品个数n=5，物品重量w[n]={0,2,2,6,5,4},物品价值V[n] = {0,6,3,5,4,6}，总重量c=10.
(第0位置为0不参与计算，只是便于与后面的下标进行统一，无特别用处)
最优值分析过程分析：
背包中的物品设为空，首先，对物品i放入背包的情况做分析，即在总重量从0到10时，如何放置物品n，使得总价值最大。如果物品i的重量超过背包允许的总重量，则物品i不放入背包，此时背包中物品的总价值为0，否则，如果物品i装入背包后不超重，则装入物品i,此时背包的总价值为物品i的价值v[i].
m(i,j) i:放的物品是i,i+1,i+2……n j:背包当前能够承受的重量
1、从头切: m(i,j)
i == n j>=Wn Vn:0 //背包当前能够承受的重量大于物品i的重量，就返回总价值Vn,否则返回0.
i
int Knapsack(int *W,int *V,int i,int j,int c)
{
if(i == j)
{
if(c >= W[i])
return V[i];
else
return 0;
}
else
{
if(c < W[i])
Knapsack(W,V,i+1,j,c);//当前背包能够承受的重量小于物品i的重量，物品i不放入
else/*背包当前能够承受的重量大于物品i的重量，选择放入物品i和不放入物品i中总价值最大的*/
{
//不放入物品i,背包能够承受的重量还是c
int max1 = Knapsack(W,V,i+1,j,c);
//放入物品i，背包能够承受的重量要减去物品i的重量，总价值要加上物品i的价值
int max2 = Knapsack(W,V,i+1,j,c-W[i])+V[i];
return max1 > max2 ? max1 : max2;;
}
}
}
int main()
{
const int N = 5;
int W[N+1] = {0,2,2,6,5,4};
int V[N+1] = {0,6,3,5,4,6};
int c = 10;
int value = Knapsack(W,V,0,N,c);
printf("value = %d\n",value);
return 0;
}
2、用m表来存放已经计算过的总价值。m表为n+1行c+1列。
int **getArray(int n,int m)
{
int **c = (int**)malloc(sizeof(int *)*(n));
for(int i=0;i<n;++i)
{
c[i] = (int *)malloc(sizeof(int)*(m));
memset(c[i],0,sizeof(int)*(m));
}
return c;
}
void freeArray(int **c,int n)
{
for(int i=0;i<n;i++)
free(c[i]);
free(c);
}
void printArray(int **arr,int n,int m)
{
for(int i=0;i<n;i++)
{
for(int j=0;j<m;j++)
printf("%d ",arr[i][j]);
printf("\n");
}
printf("\n");
}
int Knapsack(int *W,int *V,int i,int j,int c,int **m)
{
if(i == j)
{
if(c >= W[i])
m[i][c] = V[i];
else
m[i][c] = 0;
}
else
{
if(c < W[i])//当前背包能够承受的重量小于物品i的重量
m[i][c] = Knapsack(W,V,i+1,j,c,m);//不放入物品i
else//当前背包能够承受的重量大于物品i的重量
{
int max1 = Knapsack(W,V,i+1,j,c,m);//不放入物品i;
int max2 = Knapsack(W,V,i+1,j,c-W[i],m)+V[i];//放入物品i
m[i][c] = max1 > max2 ? max1 : max2;//选择放入物品i和不放入物品i中总价值最大的。
}
}
return m[i][c];
}
void BackPrint(int *W,int **m,int n,int c,int *X)
{
int i;
for(i=1;i<n;++i)
{
if(i+1<n && m[i][c]!=m[i+1][c])//说明放入了物品i
{
X[i] = true;
c -= W[i];
}
}
if(m[i-1][c] != 0)
X[i-1] = true;
}
int main()
{
const int N = 5;
int W[N+1] = {0,2,2,6,5,4};
int V[N+1] = {0,6,3,5,4,6};
int X[N+1] = {0,0,0,0,0,0};
int c = 10;
int **m = getArray(N+1,c+1);
int value = Knapsack(W,V,0,N,c,m);
printf("value = %d\n",value);
//printArray(m,N+1,c+1);
BackPrint(W,m,N+1,c,X);
for(int i=1;i<=N;i++)
if(X[i])
cout<<i<<": w = "<<W[i]<<" v = "<<V[i]<<endl;
freeArray(m,N+1);
return 0;
}
3、从尾切
m(i,j) i == 1 j>=W1 ？ V1:0
i<n j<Wi m(i-1,j)
i<n j>=Wi Max(m(i-1,j-wi)+Vi,m(i-1,j))
int Knapsack(int *W,int *V,int i,int c,int **m) //递归
{
if(i == 1)
{
if(c > W[i])
m[1][c] = V[i];
else
m[1][c] = 0;
}
else
{
if(c < W[i])
{
m[1][c] = Knapsack(W,V,i-1,c,m);
}
else
{
int max1 = Knapsack(W,V,i-1,c,m);
int max2 = Knapsack(W,V,i-1,c-W[i],m) + V[i];
m[1][c] = max1 > max2 ? max1 : max2;
}
}
return m[1][c];
}
int Knapsack(int *W,int *V,int n,int c,int **m) //非递归
{
int i = n;
int j;
/*采用从底到顶的顺序来设置m[i][j]的值 先放W[n]*/
for(j=1;j<=c;j++)
{
if(j >= W[n])
m[n][j] = V[n];
else //j小于w[n],所对应的值设为0，否则就为可以放置
m[n][j] = 0;
}
/* 对剩下的n-1个物品进行放置 */
for(i = n-1;i>=1;i--)
{
for(int j=1;j<=c;++j)
{
if(j < W[i]) //如果j < w[i]则，当前位置就不能放置，它等于上一个位置的值。
m[i][j] = m[i+1][j];
else //比较到底是放置之后的值大，还是不放置的值大，选择其中较大
{
int max1 = m[i+1][j];
int max2 = m[i+1][j-W[i]]+V[i];
m[i][j] = max1 > max2 ? max1 : max2;
}
}
}
return m[1][c];
}
void BackPrint(int *W,int **m,int n,int c,int *X)
{
int i;
for(i=1;i<n;++i)
{
if(i+1<n && m[i][c]!=m[i+1][c])//说明放入了物品i
{
X[i] = true;
c -= W[i];
}
}
if(m[i-1][c] != 0)
X[i-1] = true;
}
int main()
{
const int N = 5;
int W[N+1] = {0,2,2,6,5,4};
int V[N+1] = {0,6,3,5,4,6};
int X[N+1] = {0,0,0,0,0,0};
int c = 10;
int **m = getArray(N+1,c+1);
int value = Knapsack(W,V,N,c,m);
printf("value = %d\n",value);
printArray(m,N+1,c+1);
BackPrint(W,m,N+1,c,X);
for(int i=1;i<=N;i++)
if(X[i])
cout<<i<<": w = "<<W[i]<<" v = "<<V[i]<<endl;
freeArray(m,N+1);
return 0;
}