算法代码（背包+排序）

谁借莪１个温暖的怀抱￠ 2022-12-01 01:21 65阅读 0赞

## 背包问题 ##

### 0-1 背包 ###

import java.util.Scanner;
    //0-1背包
    public class Packet01 { 
        public static void main(String[] args) { 
            Scanner in=new Scanner(System.in);
            int capacity=in.nextInt();//背包容量
            int n=in.nextInt();//物品个数
            int[][] wv=new int[n][2];//n个物品的 w,v
            for(int i=0;i<wv.length;i++){ 
                wv[i][0]=in.nextInt();//物品 w
                wv[i][1]=in.nextInt();//物品v
            }
            int res=package01(wv,capacity);
            System.out.println(res);
        }
        public  static  int package01(int[][] wv,int capacity){ 
            int n=wv.length;//物品个数
            int[] dp=new int[capacity+1];//dp[i] 容量为i时，背包的最大价值
            for(int i=0;i<n;i++){ 
                //从第1个物品开始
                for (int j=capacity;j>=wv[i][0];j--){ 
                    //背包容量为j时，前i个物品的最大价值
                    dp[j]=Math.max(dp[j],dp[j-wv[i][0]]+wv[i][1]);
                }
            }
            return dp[capacity];
        }
    }

### 完全背包 ###

import java.util.Scanner;
    //完全背包
    public class PackagePerfect { 
        public static void main(String[] args) { 
            Scanner in =new Scanner(System.in);
            int capacity=in.nextInt();背包容量
            int n=in.nextInt();//物品个数
            int[][] wv=new int[n][2];//物品w,v
            for (int i=0;i<wv.length;i++){ 
                wv[i][0]=in.nextInt();
                wv[i][1]=in.nextInt();
            }
            int maxvalue=packetPerfect(wv,capacity);
            System.out.println(maxvalue);
    
        }
        public  static int packetPerfect(int[][] wv,int capacity){ 
            int n=wv.length;//物品个数
            int[] dp=new int[capacity+1];//dp[i] 容量为i时，背包的最大价值
            for (int i=0;i<n;i++){ 
                for(int j=wv[i][0];j<=capacity;j++){ 
                    dp[j]=Math.max(dp[j],dp[j-wv[i][0]]+wv[i][1]);
                }
            }
            return dp[capacity];
        }
    }

### 多重背包 ###

package com.algorithm;
    
    import java.util.Scanner;
    //多重背包
    public class PacketCover { 
        public static void main(String[] args) { 
            Scanner in =new Scanner(System.in);
            int capacity=in.nextInt();背包容量
            int n=in.nextInt();//物品种类数
            int[][] wv=new int[n][2];//物品w,v
            int[] num=new int[n];//每种物品的数量
            for (int i=0;i<wv.length;i++){ 
                wv[i][0]=in.nextInt();
                wv[i][1]=in.nextInt();
            }
            for(int i=0;i<num.length;i++){ 
                num[i]=in.nextInt();
            }
            int maxvalue=packetPerfect(wv,capacity,num);
            System.out.println(maxvalue);
    
        }
        public  static int packetPerfect(int[][] wv,int capacity,int[] num){ 
            int n=wv.length;//物品个数
            int[] dp=new int[capacity+1];//dp[i] 容量为i时，背包的最大价值
            for (int i=0;i<n;i++){ 
    
                for(int j=capacity;j>=wv[i][0];j--){ 
    
                    for(int k=0;k<=num[i] && j-k*wv[i][0]>=0;k++){ 
                        dp[j]=Math.max(dp[j],dp[j-k*wv[i][0]]+k*wv[i][1]);
                    }
                }
    
            }
            return dp[capacity];
        }
    }

## 排序算法 ##

### 优化的快排 ###

package com.sort;
    //优化快排
    public class QuickSort { 
        public static final int N=10;
        public static void main(String[] args) { 
            int[] arr=new int[]{ 1,4,6,7,6,6,7,6,8,6,2,5,6};
            quickSort(arr,0,arr.length-1);
            System.out.println("排序完成的序列：");
            for(int k=0;k<arr.length;k++){ 
                System.out.print(arr[k]+" ");
            }
    
        }
        // 三数取中+插入排序+聚合重复元素
        public  static void quickSort(int[] arr,int l,int h){ 
            //边界处理
            if(l>h)return;
            //如果待排序序列元素小于10，则使用插入排序
           if(h-l+1<N){ 
               insertSort(arr,l,h);
                return;
          }else{ 
                //否则，使用快速排序
                //选择枢纽
                int base=selectBaseOfThree(arr,l,h);
                int i=l,j=h;
                while(i<j){ 
                    while (i<j && arr[j]>base)j--;
                    if(i<j){ 
                        arr[i]=arr[j];
                        i++;
                    }
                    while(i<j && arr[i]<=base)i++;
                    if(i<j){ 
                        arr[j]=arr[i];
                        j--;
                    }
                }
                arr[i]=base;
                System.out.println("一趟排序后，聚合前的序列：");
                for(int k=0;k<arr.length;k++){ 
                    System.out.print(arr[k]+" ");
                }
                System.out.println();
                //一趟排序结束，将于base相同的元素聚合在一起
                int r=gather(arr,l,i);
                System.out.println("聚合后的序列：");
                for(int k=0;k<arr.length;k++){ 
                    System.out.print(arr[k]+" ");
                }
                System.out.println();
                quickSort(arr,l,r);
                quickSort(arr,i+1,h);
            }
        }
        //将和base相同的元素聚合在一起
        public  static  int gather(int[] arr,int l,int r){ 
            int index=r;
            for(int i=r-1;i>=l;i--){ 
                if(arr[i]==arr[r]){ 
                    if(arr[i+1]==arr[r]){ 
                        index=i;
                        continue;
                    }
                    for(int j=i+1;j<index;j++){ 
                        arr[j-1]=arr[j];
                    }
                    arr[index-1]=arr[r];
                    index--;
                }
            }
            System.out.println("index-1:"+(index-1));
            return index-1;
        }
        //选择枢纽
        public  static  int  selectBaseOfThree(int[] arr,int l,int h){ 
            int mid=l+((h-l)>>1);
            if(arr[mid]>arr[h]){ 
                swap(arr,mid,h);
    
            }
            if(arr[l]>arr[h]){ 
                swap(arr,l,h);
            }
            if(arr[mid]>arr[l]){ 
                swap(arr,mid,l);
            }
            return arr[l];
        }
        public static void swap(int[] arr,int n,int m){ 
            int tem=arr[n];
            arr[n]=arr[m];
            arr[m]=tem;
        }
    
        //在l-h范围进行插入排序
        public  static  void insertSort(int[] arr,int l,int h){ 
            for(int i=l+1;i<=h;i++){ 
              int tem=arr[i];
              int left=i-1;
              while(left>=l && arr[left]>tem){ 
                  arr[left+1]=arr[left];
                  left--;
              }
              arr[left+1]=tem;
            }
        }
    }

### 选择排序 ###

package com.sort;
    //选择排序
    public class SelectSort { 
        public static void main(String[] args){ 
            int[] arr = new int[]{ 1, 4, 6, 2, 8, 6,9};
            selectSort(arr,0,arr.length-1);
            System.out.println("排序完成的序列：");
            for (int k = 0; k < arr.length; k++) { 
                System.out.print(arr[k] + " ");
            }
    
        }
        public  static  void selectSort(int[] arr,int l,int r){ 
            for(int i=l;i<r;i++){ 
                int min=i;
                for(int j=i+1;j<=r;j++){ 
                    if(arr[j]<arr[min]){ 
                        min=j;
                    }
                }
                swap(arr,i,min);
            }
    
        }
        public  static void swap(int[] arr,int n,int m){ 
            int tem=arr[n];
            arr[n]=arr[m];
            arr[m]=tem;
        }
    }

### 冒泡 ###

package com.sort;
    //冒泡排序
    public class Maopao { 
        public static void main(String[] args) { 
            int[] arr = new int[]{ 1, 4, 6, 7, 6, 6, 7, 6, 8, 6, 2, 5, 6};
            maoPaoSort(arr);
            System.out.println("排序完成的序列：");
            for (int k = 0; k < arr.length; k++) { 
                System.out.print(arr[k] + " ");
            }
    
        }
        public static  void maoPaoSort(int[] arr){ 
            if(arr.length<2)return;
            for(int i=arr.length-1;i>0;i--){ 
                int flag=0;
                for(int j=0;j<i;j++){ 
                    if(arr[j]>arr[j+1]){ 
                        flag=1;
                        swap(arr,j,j+1);
                    }
    
                }
                for (int k = 0; k < arr.length; k++) { 
                    System.out.print(arr[k] + " ");
                }
                System.out.println();
                if(flag==0)break;
            }
        }
        public  static void swap(int[] arr,int n,int m){ 
            int tem=arr[n];
            arr[n]=arr[m];
            arr[m]=tem;
        }
    
    }

### 堆排序 ###

package com.sort;
    //堆排序
    public class DumpSort { 
        public  static  int len;
        public static void main(String[] args) { 
            int[] arr = new int[]{ 1, 4, 6, 2, 8, 6,9,3};
            dumpSort(arr);
            System.out.println("排序完成的序列：");
            for (int k = 0; k < arr.length; k++) { 
                System.out.print(arr[k] + " ");
            }
    
        }
    
        public  static  void dumpSort(int[] arr){ 
            len=arr.length;
            if(len<2)return;
            //构建大顶堆
            buildMaxDump(arr);
            //不断将堆顶与最后元素交换
            while(len>0){ 
                swap(arr,0,len-1);
                len--;
                adjustDump(arr,0);
            }
        }
    
        public static  void buildMaxDump(int[] arr){ 
            for(int i=(len/2-1);i>=0;i--){ 
                adjustDump(arr,i);
            }
        }
        public  static  void adjustDump(int[] arr,int i){ 
            int max=i;
            if((i*2+1)<len && arr[i*2+1]>arr[max]){ 
                max=i*2+1;
            }
            if((i*2+2)<len && arr[i*2+2]>arr[max]){ 
                max=i*2+2;
            }
            if(max!=i){ 
                swap(arr,i,max);
                adjustDump(arr,max);
            }
        }
        public static void swap(int[] arr,int n,int m){ 
            int tem=arr[n];
            arr[n]=arr[m];
            arr[m]=tem;
        }
    
    
    }

### 插入排序 ###

package com.sort;
    //插入排序
    public class InsertSort { 
        public static void main(String[] args) { 
            int[] arr = new int[]{ 1, 4, 6, 7, 6, 6, 7, 6, 8, 6, 2, 5, 6};
           insertSort(arr,0,arr.length-1);
            System.out.println("排序完成的序列：");
            for (int k = 0; k < arr.length; k++) { 
                System.out.print(arr[k] + " ");
            }
    
        }
        public static void insertSort(int[] arr,int l,int r){ 
            for(int i=l+1;i<=r;i++){ 
                int tem=arr[i];
                int left=i-1;
                while(left>=l && arr[left]>tem){ 
                    arr[left+1]=arr[left];
                    left--;
                }
                arr[left+1]=tem;
            }
        }
    }

### 归并排序 ###

package com.sort;
    
    import java.util.Arrays;
    
    //归并排序
    public class MergeSort { 
    
        public static void main(String[] args) { 
            int[] arr = new int[]{ 1, 4, 6, 2, 8, 6,9,3};
           int[] res=mergeSort(arr);
            System.out.println("排序完成的序列：");
            for (int k = 0; k < res.length; k++) { 
                System.out.print(res[k] + " ");
            }
    
        }
    
        public static int[] mergeSort(int[] array) { 
            if (array.length < 2) return array;
            int mid = array.length / 2;
            int[] left = Arrays.copyOfRange(array, 0, mid);
            int[] right = Arrays.copyOfRange(array, mid, array.length);
            return merge(mergeSort(left), mergeSort(right));
        }
    
        public static int[] merge(int[] left, int[] right) { 
            int[] result = new int[left.length + right.length];
            for (int index = 0, i = 0, j = 0; index < result.length; index++) { 
                if (i >= left.length)
                    result[index] = right[j++];
                else if (j >= right.length)
                    result[index] = left[i++];
                else if (left[i] > right[j])
                    result[index] = right[j++];
                else
                    result[index] = left[i++];
            }
            return result;
        }
    }

### 希尔排序 ###

package com.sort;
    //希尔排序
    public class ShellSort { 
        public static void main(String[] args) { 
            int[] arr = new int[]{ 20, 4, 7, 10, 8, 6,9};
            shellSort(arr);
        }
        public  static  void shellSort(int[] arr){ 
            if(arr.length<2)return;
            int gap=arr.length/2;
            while (gap>0){ 
                for(int i=gap;i<arr.length;i++){ 
                    int temp=arr[i];
                    int pre=i-gap;
                    while(pre>=0 && arr[pre]>temp){ 
                        arr[pre+gap]=arr[pre];
                        pre=pre-gap;
                    }
                    arr[pre+gap]=temp;
                }
                System.out.println("增量为："+gap);
                for (int k = 0; k < arr.length; k++) { 
                    System.out.print(arr[k] + " ");
                }
                System.out.println();
                gap=gap/2;
            }
        }
    }