public class HuiSuBeiBao
{
static int n = 5;
static int capacity = 10;
static int[] weight = {6,5,4,2,1};
static double[] value = {5,3,5,3,2};
static int maxValue = 0;
static int tempValue;
static int tempWeight;
static int[] way = new int[n];
static int[] bestWay = new int[n];
public static void BackTrack(int t)
{
if(t>n-1)
{
if(tempValue > maxValue)
{
maxValue = tempValue;
for(int i=0;i<n;i++)
{
bestWay[i] = way[i];
}
}
return;
}
if(tempWeight + weight[t] <= capacity)
{
tempWeight += weight[t];
tempValue += value[t];
way[t] = 1;
BackTrack(t+1);
tempWeight -= weight[t];
tempValue -= value[t];
way[t] = 0;
}
if( Bound(t+1) >= maxValue)
{
BackTrack(t+1);
}
}
public static double Bound(int k)
{
double maxLeft = tempValue;
int leftWeight = capacity - tempWeight;
while(k <= n-1 && leftWeight > weight[k] )
{
leftWeight -= weight[k];
maxLeft += value[k];
k++;
}
if( k <= n-1)
{
maxLeft += value[k]/weight[k]*leftWeight;
}
return maxLeft;
}
public static void main(String[] args)
{
BackTrack(0);
System.out.println("能够取到的最大价值为:"+maxValue);
System.out.println("1代表选,0代表不选");
System.out.println("取出的方法为:");
for(int i : bestWay)
{
System.out.print(i+" ");
}
System.out.println();
}
}