牛牛的背包问题

Java实现的中途相遇法

1. 分析：
   由于直接进行二进制枚举的算法时间复杂度太高显然是不可行的，那么我们可以借助中途相遇法的思想，将n个零食分为两部分[1, n/2]，(n/2, n]，然后枚举前一部分的所有可能取法，将这些可能取法用一个集合left记录下来，然后枚举剩余的后一部分的所有可能取法，对于后一部分的可能取法获得其体积值，然后用tmp=背包容量值-当前体积值，我们只需要在前一部分的所有可能取法数组种找到第一个>tmp的下标，此时就知道在前一部分有多少个是满足条件的，将下标即个数记录到结果中。
   Tips：注意结果用long

算法实现：
(0). 将n件物品分为两部分，保存前一部分所有可能取法的体积值
(1). 遍历剩余的后一部分的可能取法
(2). 对于每种状态计算背包容量与当前体积值的差值tmp，然后在集合left中二分查找第一个大于tmp的值的下标，此时下标就是在前一部分中有多少种状态与当前体积相加之和满足不超过背包容量的个数。
(3). 输出最终结果

import java.util.ArrayList;
import java.util.Collections;
import java.util.Scanner;

/**
 * @version: 1.0
 */
public class Main8 {
    /*    static int  num = 0;
        public static void main(String[] args) {
            Scanner sc = new Scanner(System.in);
            int n = sc.nextInt();//零食袋数
            int w = sc.nextInt();//背包载重
            int v[] = new int[n];//每袋零食的重量
            long total = 0;
            for (int i = 0;i<n;i++){
                v[i] = sc.nextInt();
                total+=v[i];
            }
            if (total<=w)
                System.out.println((int)Math.pow(2,n));
            else{
                h(v,n,0,*//*(long)*//*0,w);
            System.out.println(num);
        }
        sc.close();
    }
    private static void h(int v[],int n,int i,long sum,int w){
        if(i == n && sum <= w){
            num++;
            return;
        }
        if (sum > w) return;
        h(v, n, i+1, sum, w);
        h(v, n, i+1, sum+v[i], w);
    }*/
    public static void main(String[] args) {
        int  num = 0;
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();//零食袋数
        int w = sc.nextInt();//背包载重
        int v[] = new int[n/2];//前1/2每袋零食的重量
        ArrayList<Long> left = new ArrayList<>();
        for (int i = 0;i<n/2;i++)
            v[i] = sc.nextInt();
        h(v,n/2,0,0,left,w);
        Collections.sort(left);
        int vr[] = new int[n-n/2];//后1/2每袋零食的重量
        for (int i = 0;i<(n-n/2);i++)
            vr[i] = sc.nextInt();
        ArrayList<Long> right = new ArrayList<>();
        h2(vr,n-n/2,0,0,right,w);
        for (long r: right)
            num+=getMin(left,r);
        System.out.println(num);
        sc.close();
    }
    private static void h(int v[],int n,int i,long sum,ArrayList<Long> left,int w){//将重量方法left集合
        if (sum>w) return;//总重量大于载重w，直接舍弃
        if(i == n){
            left.add(sum);
            return;
        }
        h(v, n, i+1, sum,left,w);
        h(v, n, i+1, sum+v[i],left,w);
    }
    private static void h2(int vr[],int n,int i,long sum,ArrayList<Long> right,int w){//将剩余重量放入right集合
        if (sum>w) return;//总重量大于载重w，直接舍弃
        if(i == n){
            right.add(w-sum);
            return;
        }
        h2(vr, n, i+1, sum,right,w);
        h2(vr, n, i+1, sum+vr[i],right,w);
    }

    private static int getMin(ArrayList<Long> arr, long a) {//二分查找到第一个大于a的索引
        int l = 0;
        int r = arr.size()-1;
        int mid;
        while (l<=r){
            mid = (l+r)/2;
            if (arr.get(mid) > a) r = mid-1;
            else l = mid+1;
        }
        return l;
    }
}

之前暴力破解AC率为80%， 加了分析是否出现， 所有的零食都可以放入书包的情况判断后， 通过了，好的吧， 个人感觉， 有点投机取巧了

import java.util.Scanner;
public class Main{
    public static void main(String [] args)
    {
        //读取数据
        Scanner sc = new Scanner(System.in);
        
        int n = sc.nextInt();    //零食的数量
        int w = sc.nextInt();    //背包容量
        
        int [] v = new int [n];
        for(int i=0; i<n; i++)
        {
            v[i] = sc.nextInt();
        }
        //太多了， 暴力破解失败， 加上快排进行筛选
        que(v,0, n-1);
        int sum = 0;
        int i = 0;
        for(i=0; i<n;i++)
        {
            if(sum > (Integer.MAX_VALUE-v[i]))
                break;
            sum += v[i];
            
            if(sum > w )
                break ;
        }
        if(i == n  )
        {
            int r = (int)Math.pow(2, i);
            System.out.println(r);
            return ;
        }
        
        int res = getRes(v, 0, 0, w)+1;
        System.out.println(res);
        
    }
    
    public static void que(int [] v, int low, int high){
        if(low < high && low >= 0 && high <v.length)
        {
            int mid = getPar( v, low , high);
            que(v, mid+1, high);
            que(v, low, mid-1);     
        }
       
    }
    public static int getPar(int [] v, int low , int high)
    {
         
              int temp = v[low];
        while(low < high && low >= 0 && high <v.length)
        {
            while(low < high &&v[high] >= temp)
            {
                high--;
            }
            v[low]=v[high];
            while(low < high && v[low] <= temp)
            {
                low++;
            }
            v[high] = v[low];
        }
        v[low] = temp;
        return low;
    //     }
      //  return -1;
       
        
    }
    
    public static  int getRes(int [] v, int cur, int sum,int w)
    {
        if(sum > w)
            return 0;
        int res = 0;
        while(cur < v.length)    
        {
            
            int temp = sum;
              int value =   Integer.MAX_VALUE - sum ;
            sum += v[cur];        //sum溢出怎么检测
            int c = sum -v[cur];
            if(value < v[cur])
            {
                return res;
            }
            /*
            if(temp == (sum-v[cur]) && sum <= w)
                res += 1;
            if(temp == (sum-v[cur]))
                res += getRes(v, cur+1, sum, w);*/
          //  if(value >= v[cur])
            //{
                if(sum <= w)
                    res += 1;
                res += getRes(v, cur+1, sum, w);
           // }
           // sum -= v[cur];
            sum = temp;
            cur++;
        }
        return res;
    }
}

利用回溯算法思想解决背包问题。（递归穷举+剪枝）

import java.util.*;
public class Main{
    static int res = 0;//种类计数
    //n:零食的数量
    //w:背包的容量
    //v:每袋零食的体积
    //i:考虑到第几个零食了
    //cw:目前背包内已有的零食总重（必须定义为long，否则求和溢出，AC80%）
    public static void solution(int n,int w,int[] v,int i,long cw){
        //回溯算法思想
        if(i<n){  //未全部考虑完
            solution(n,w,v,i+1,cw);//不放当前i的零食，直接考虑i+1
            if(cw+v[i]<=w){ //放当前i的零食
                res++;
                solution(n,w,v,i+1,cw+v[i]);
            }
        }
        
    }
    public static void main(String[] args){
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        int w = scanner.nextInt();
        int[] v = new int[n];
        long sum = 0;
        for(int i=0;i<n;i++){
            v[i]=scanner.nextInt();
            sum=sum+v[i];
        }
        if(sum<=w) 
            System.out.println((int)Math.pow(2,n));
        else{
            solution(n,w,v,0,0);
            System.out.println(res+1);
        }
    }
}

Java解答：利用的递归的思想。

import java.util.*;
 
public class Main {
    public static long result = 1;
    public static void main(String[] args) {
        Scanner input = new Scanner(System.in);
        int n = input.nextInt();
        long w = input.nextInt();
        long[] v = new long[n];
        long sum = 0;
        for (int i = 0; i < n; i++) {
            v[i] = input.nextInt();
            sum = sum + v[i];
        }
        if (sum <= w) {
            System.out.println((int) Math.pow(2, n));
        } else {
            state(v, 0, w, 0);
            System.out.println(result);
        }
    }
    public static void state(long[] v,int index, long w, long current){
        if (index == v.length)
            return;
        if (current + v[index] <= w){
            result++;
            state(v, index+1,w,current+v[index]);
        }
        state(v,index+1,w,current);
    }
}

背包问题常规思路是用dp来做，但此题背包容量极大，申请dp空间只能AC 20%；

另一种思路是用dfs递归求解，复杂度2^n，对于此题n<30,可以AC;

这里提供另外一种AC思路，分治法思想，如果n<20，直接枚举出答案；n如果大于20，将n分成两半，分别枚举出两半的结果，由加法原理和乘法原理计算得到最后的答案。

import java.util.*;

import static java.lang.System.in;

 

public class Main {

    public static void main(String[] args) {

        Scanner sc = new Scanner(in);

        int n = sc.nextInt();

        int w = sc.nextInt();

 

        int[] vs = new int[n];

        for (int i = 0; i < n; i++) {

            vs[i] = sc.nextInt();

        }

        System.out.println(dpProcess(vs, w));

    }

 

    public static int dpProcess(int[] vs, int w) {

        int len = vs.length;

        int ans = 0;

        if (len < 20) {

            for (int i = 0; i < (1 << len); i++) {

                long weight = 0;

                for (int j = 0; j < len; j++) {

                    if ((i & (1 << j)) != 0) {

                        weight += vs[j];

                    }

                }

                if (weight <= w) {

                    ans++;

                }

            }

            return ans;

        }

        //如果大于20，则切两半 0 ~ 14,15 ~ n

        HashMap<Long, Integer> map = new HashMap<>();

        for (int i = 0; i < (1 << 15); i++) {

            long weight = 0;

            for (int j = 0; j < 15; j++) {

                if ((i & (1 << j)) != 0) {

                    weight += vs[j];

                }

            }

            if (weight <= w) {

                map.put(weight, map.getOrDefault(weight, 0) + 1);

            }

        }

        HashMap<Long, Integer> mapAnother = new HashMap<>();

        for (int i = 0; i < (1 << (len - 15)); i++) {

            long weight = 0;

            for (int j = 0; j < len - 15; j++) {

                if ((i & (1 << j)) != 0) {

                    weight += vs[15 + j];

                }

            }

            if (weight <= w) {

                mapAnother.put(weight, mapAnother.getOrDefault(weight, 0) + 1);

            }

        }

        ArrayList<Map.Entry<Long, Integer>> array = new ArrayList<>(map.entrySet());

        Collections.sort(array, (o1, o2) -> (int) (o1.getKey() - o2.getKey()));

        TreeMap<Long, Integer> resMap = new TreeMap<>();

        int temp = 0;

        for (int i = 0; i < array.size(); i++) {

            temp += array.get(i).getValue();

            resMap.put(array.get(i).getKey(), temp);

        }

 

        long tempL = 0;

        int retAns = 0;

        for (Map.Entry<Long, Integer> item : mapAnother.entrySet()) {

            tempL = w - item.getKey();

            retAns += resMap.floorEntry(tempL).getValue() * item.getValue();

        }

        return retAns;

    }

}