编辑代码

/**
 * @author WUHAO
 * @create 2022-12-06 16:36
 */
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();
    }
}