背包所有可能放置方法（C++）

回溯法求解，每次每個物品都有放與不放兩種情況，每次放時要判斷是否能放。

#include<iostream>

using namespace std;

//回溯函數定義，rw 剩餘容量，i第i個物品，v體積數組，number到第i個物品處有幾種裝法，n物品總數

int backtrack(int rw, int i, int *v, int number, int n);

//回溯法背包問題

//背包容量w

//n個零食，每個零食體積為v[i]

//輸入：

//n w

//v[0]...v[n-1]

//輸出

//最多幾種裝法，什麼也不裝也算一種

//例如，輸入為

//3 10

//1 2 4

//輸出為

//8

//

//例如，輸入為

//3 10

//1 9 4

//輸出為

//6

//

//例如，輸入為

//3 10

//5 5 3

//輸出為

//7

int main() {

    int n;

    cin >> n;

    int w;

    cin >> w;

    int* v = new int[n];

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

        cin >> v[i];

    }

    //排序，從小到大

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

        for (int j = i; j < n; j++)

        {

            if (v[i] > v[j]) {

                int tmp = v[i];

                v[i] = v[j];

                v[j] = tmp;

            }

        }

    }

    int result = 1;

    result=backtrack(w,0,v,result,n);

    cout << result;

    system("pause");

    return 0;

}

//rw 剩餘容量，i第i個物品，v體積數組，number到第i個物品處有幾種裝法，n物品總數

int backtrack(int rw,int i,int *v,int number,int n) {

    int tmp1 = 0;//i裝的方法數

    int tmp2 = 0;//i不裝的方法數

    if (i == n) {

        //裝與不裝都是一種方法

        return 1;

    }

    number++;

    if (rw >= v[i]) tmp1=backtrack(rw-v[i],i+1,v,number,n);

    number--;

    tmp2=backtrack(rw , i + 1, v, number, n);

    return tmp1 + tmp2;//傳回放與不放兩種方法的總和

}