01背包問題（二進制解法）

題目

有N件物品和一個容量為V的背包。第i件物品的重量是w[i]。求解将哪些物品裝入背包可使這些物品的重量總和不超過背包容量的最大重量。

基本思路

首先，我想分析一下這個題目大暴力時，複雜度為什麼為N^2。如果大暴力，本題目的預算次數實際為pow(2,n)-1。 初等數學思路（大佬請忽略）： 本題中一共給定n個物品，如果要放入1個物品時為N種； 如果要放入2個時候，需要從N個中取出A2N個物品； 是以該題目為N個物品從1到N的全排列的前N項和； （PS：如果任意一個物品體積都大于背包體積時，是以存在所有物品都不選擇的坑） 是以由初等數學知識可知，該題目的實際運算次數為pow(2,n)-1； 二進制思路：先上思路圖

首先需要先解釋一下圖檔，圖檔照片中的紅色表示選擇a[i-1]位置的物品，綠色則表示不選擇。 再進行思路解釋，物品中共有pow(2,n)-1個線段。每個線段回溯到頂端，就為一種方法解決方法，如果把要與不要，分别抽象為1和0，則實作了控制是否收取本位物品的方法，在進行判斷每次加法之後是否存在一個大數，記錄大數就可以，當不滿足是跳過就可以。 （PS：當出現問題拓展的時候，可以記錄滿足條件時候的十位數就可以了）。

//
//  main.cpp
//  01背包問題（二進制）
//  Created by MaLker on 2017/3/2.
//  Copyright © 2017年 MaLker. All rights reserved.
//

#include <iostream>
#include <math.h>
#include <algorithm>
using namespace std;
int main(int argc, const char * argv[]) {
    int n,a[10],biger;
    while (scanf("%d%d",&n,&biger)!=EOF) {
        for (int i=0; i<n; i++) {//我是輸入的資料
            scanf("%d",&a[i]);
        }
        int t = pow(2, n)-1/*計算的次數，并且存儲*/,midi,sum = 0,max1 = 0;
        for (int i = 1 ; i < t; i++) {
            midi = i/*i的中間值，防止i被污染*/;
            for (int tm = 0; tm < n; tm++) {
                if ((midi>>1)&1) {/*按位運算取對應物品位置的取舍*/
                    sum+=a[tm];
                }
                if(sum <= biger)
                max1 = max(max1,sum);/*篩選判斷*/
                else
                    continue;/*最水的優化*/
            }
            sum=0;/*初始化相應位置的求和*/
        }
        printf("%d\n",max1);
    }
    return 0;
}
//if((i>>1)&1)