动态规划法(四)——0/1背包问题
问题描述
有n个物体，重量分别是w0~wn-1，每个物体放入背包后可获得的收益分别为p0~pn-1，背包载重为M，且所有物体要么放要么不放，不能只放一部分。求如何放物体可以得到最高的收益。
问题分析
设f(i,m)表示第i步背包的总收益，其中i表示当前进行到了第i步，m为当前背包载重，则当前第i步只有两种选择：
- 将第i个物体放入背包 此时背包总收益就变成f(i-1,m-wi)+wi。
- 第i个物体不放入背包 此时背包总收益就是f(i-1,m)。
第i步究竟怎么选择，知道就取决于这两种选择那个结果更大。因此要分别计算者两种情况的值，选较大者作为第i步的结果。 这就是一个典型x的递归。
代码实现
// 表示每一个物体是否放入背包
boolean[] isAdd = new boolean[n];
// 存储每个物体的重量
int[] weight = new int[n];
// 存储每个物体的收益
int[] p = new int[n];
/**
* 0/1背包问题的递归函数
* @param i : 当前是第几步
* @param m : 当前背包载重
* @return 最大收益
*/
int knap( int i, int m ){
if ( i==-1 ) return 0;
if ( weight[i]>m )
return knap( i-1, m );
int a = knap(i-1,m);
int b = knap(i-1,m-weight[i])+p[i];
if ( a>b )
return a;
else{
isAdd[i] = true;
return b;
}
}举报
腾讯云开发者
