鵬哥

問題描述

假設有一個能裝入總體積為T的背包和n件體積分別為w1,w2…wn.的物品，能否從n件物品中挑選若干件恰好裝滿背包，即使w1+w2+…+wn=T,要求找出所有滿足上述條件的解.

---

解決思路

回溯法

假設一個背包可背的重量為s，現在有n件物品，重量分別為w1，w2，…，wn。若選取其中若干件物品的質量總和恰好為s，那么稱此背包問題有解，否在無解。

在討論這個問題時，考慮的是一件物品在背包問題中只有兩種可能
一種是不選擇wn，這樣 Knap(s,n)的解就是Knap(s,n-1)的解;
另一種是選擇wn，這樣Knap(s,n)的解就是Knap(s-wn,n-1)**的解;
這樣可以將背包問題的遞歸定義為Knap(s,n)
s= 0時，Knap(s,n)=True
s<0時，Knap(s,n)=Fals
s>0且n<1，Knap(s,n)=False
s>0且n>=1，Knap(s,n)=Knap(s,n-1)或Knap(s-wn,n-1）

具體舉個例子假設
假設T=10;w={1,8,4,3,5,2};
此時回溯的8
滿足條件輸出方案：1432
此時回溯的2
此時回溯的3
滿足條件輸出方案：145
此時回溯的5
此時回溯的2
此時回溯的4
此時回溯的5
此時回溯的2
此時回溯的3
此時回溯的2
此時回溯的5
此時回溯的2
此時回溯的1
滿足條件輸出方案：82
此時回溯的2
此時回溯的8
此時回溯的2
此時回溯的3
此時回溯的5
此時回溯的2
此時回溯的4
滿足條件輸出方案：352
此時回溯的2
此時回溯的5
此時回溯的2
此時回溯的3
此時回溯的2
此時回溯的5
此時回溯的2

代碼展示

import java.util.Arrays;
public class Package {
    static class MyList {
        //定義Object類型的數組
        Object[] data ;
        //統計變量，用于統計數組元素的真實個數
        int size;
        public MyList() {
            //初始化長度為10
            this(50);
        }
        MyList(int length){
            //通過構造方法指定數組的長度
            data = new Object[length];
        }
        //長度
        public int getLength(){
            return size;
        }
        //為了方便看效果，我們覆寫toString()方法
        //為了打印真實的數組內容，除去空余的默認值
        @Override
        public String toString() {
            //構建一個新的數組，長度為size
            Object[] newdata = new Object[size];
            //將data中的元素拷貝到新數組中
            System.arraycopy(data, 0, newdata, 0, size);
            //利用Arrays類，將數組轉換成字符串
            return Arrays.toString(newdata);
        }
        //增
        void add(Object obj){
            //如果數組滿了
            if(size>=data.length){
                //構建一個新的數組，容量默認增加10
                Object[] newdata = new Object[data.length+10];
                //將原來的數組內容拷貝到擴容后的數組中
                System.arraycopy(data, 0, newdata, 0, size);
            }
            //將新增的元素添加在數組的末尾
            data[size] = obj;
            //數組真實長度自增1
            size++;
        }

        //查找指定元素第一次出現的索引
        public int indexOf(Object obj){
            for (int i = 0; i < size; i++) {
                if(obj.equals(data[i])){
                    return i;
                }
            }
            return -1;//沒有找到
        }

    }

    static class MyStack<E> {
        //數組的默認大小為10
         static final int DEFAULT_INIT_CAPACITY = 10;
        //底層的數組
         Object[] elements;
        //棧中的個數
         int size;
        public MyStack() {
            this(DEFAULT_INIT_CAPACITY);
        }
        public MyStack(int capacity) {
            //capacity條件檢查 ，這里我們直接拋出異常
            if (capacity <= 0) {
                throw new IllegalArgumentException("capacity <= 0");
            }

            //新建一個capacity大小的數組
            elements = new Object[capacity];

            //初始個數為0
            size = 0;
        }

        //棧是否為空
        public boolean isEmpty() {
            return size == 0;
        }

        //返回棧中的元素個數
        public int size() {
            return size;
        }

        //將一個元素壓入棧中
        public E push(E e) {
            //如果棧已滿，進行擴容
            if (size >= elements.length) {
                grow();
            }
            //擴容完后將元素e壓入棧中
            elements[size] = e;
            //別忘了size需要加 1
            size++;
            return e;
        }

        //出棧，就是將數組最后一個元素彈出
        public E pop() {
            //如果棧為空就返回null
            if (isEmpty()) {
                return null;
            }
            //拿到棧的大小
            int len = size();
            //把數組中最后一個元素保存起來
            E e = peek();
            //個數別忘了減1
            size--;
            //將最后一個元素置null
            elements[len - 1] = null;
            //返回e
            return e;
        }

        //返回最后一個元素
        public E peek() {
            int len = size();
            if (len == 0)
                throw new RuntimeException("stack is empty");
            return (E) elements[len - 1];
        }

        //擴容
        private void grow() {
            //將之前的數組保存
            int oldCapacity = elements.length;
            Object[] old = elements;
            //新的數組大小為原來數組大小的2倍
            int newCapacity = oldCapacity * 2;
            //再新建一個大小為原來數組2倍的新數組
            elements = new Object[newCapacity];
            //把以前的老的數組中的元素都移動新數組中
            for (int i = 0; i < oldCapacity; i++) {
                elements[i] = old[i];
            }

            //釋放以前的內存空間
            old = null;
        }

    }
    public static void main(String[] args) {
        MyList list = new MyList();
        int count = 0;
//        Scanner scanner = new Scanner(System.in);
//        System.out.println("請輸入的物體的體積,輸入0停止");
//        while (scanner.hasNextLine()) {
//            int a = scanner.nextInt();
//            if (a == 0) {
//                break;
//            }
//            list.add(a);
//        }
//        System.out.println("請輸入背包的大小");
//        int caption = scanner.nextInt();
//        scanner.close();
        list.add(1);
        list.add(8);
        list.add(4);
        list.add(3);
        list.add(5);
        list.add(2);
        int caption = 10;
        int length = list.size;
        MyStack<Integer> stack = new MyStack<>();
        int j = 0;
        do {
            for (int i = j; i < length && caption > 0; i++) {
                if (caption >= (int)list.data [i])//有點貪婪的思想能放下就放下
                {
                    caption -= (int) list.data[i];
                    //System.out.println(caption);
                    stack.push((Integer) list.data[i]);
                //   System.out.println("此時放置的" + list.get(i));
                }
            }
            if (caption == 0) {//合適我們就輸出
                count++;
                System.out.print("第" + count + "種方案：");
                for (Object integer : stack.elements) {
                    if(integer!=null)
                    System.out.print(integer);
                }
                System.out.println();
            }
            int temp = stack.pop();//不合適我們就回溯
            caption += temp;
            System.out.println("此時回溯的" + temp);//碰到2就回溯兩次
            j = list.indexOf(temp) +1;//從回溯的元素下一個元素開始
           // System.out.println(j);
        } while ((!stack.isEmpty())|| (j != length) );//雙指針思想
    }
    /**
     程序=算法+數據結構，但是我覺得他們雖然是相加的關系，但是
      它們在對于程序的意義上的地位應該是不相等的，應該是3,7開的
      算法占7.數據結構占3，因為一個好的算法能夠大大減小計算機解
      決問題的開銷，雖然好的數據結構也可以，但是算法的用處應該還
      是大一點，就像這里和后面的八皇后，你如果采用枚舉法的話，運算量
      將...**/
}