背包問題（Knapsack problem）

假設背包容積 W，寶物數量 N，屬性如下：
寶物1寶物2   ...   寶物N
體積v1v2...vN
價值c1c2...cN
每件寶物只有 1 件，因此只考慮不拿寶物或拿寶物入背包(有就是 0 與 1)，則策略應如何?
  1. 貪婪取 cp 值最高者：
    2. cp 值為 價值/體積 (下表除了提供寶物的體積與價值，順便把 cp 值也求出)
    寶物1寶物2寶物3寶物4寶物5寶物6
    體積311412
    價值422722
    cp值1.33221.7522
    假設背包容量 5，依照 cp 值最高者入袋，則結果是寶物 2、3、5， 價值是 6，剩下體積 2 ，只能拿寶物 6，總價值 8，但答案是寶物4 + 寶物2，總價值是 9。

  2. 貪婪取價值最高者：
    3. 寶物1寶物2寶物3寶物4寶物5
    體積31121
    價值1666116
    假設背包容量 3，依照價值最高者入袋，則結果是寶物 1 價值是 16，但答案是寶物 2、3、5 價值是 18。

  3. 貪婪取體積最小者：(裝小體積可以裝得多)
    4. 寶物1寶物2寶物3寶物4寶物5
    體積31121
    價值1966136
    假設背包容量 3，依照體積最小者入袋，則結果是寶物 2、3、5 價值是 18，但答案是寶物 1 價值是 19。

    上面所演示的貪婪法皆失敗，所以這種問題只能用暴搜。
    暴搜方式假設寶物有 n 個，則使用迴圈產生 n 個 bit 2 進制，每個 bit 表示 1 個寶物拿與不拿，最後再計算總價值。
    下面三種程式供參考：(以下假設 4 個寶物)

    使用 for 迴圈
    #include <iostream>
using namespace std;
int main() {
    int a1,a2,a3,a4;
    for(a1=0;a1<=1;a1++){
        for(a2=0;a2<=1;a2++){
            for(a3=0;a3<=1;a3++){
                for(a4=0;a4<=1;a4++){
                    cout << a1 << a2 << a3 << a4 << endl;
                }
            }
        }	
    }
    return(0);
}
    使用堆疊
    #include <iostream>
using namespace std;
#define N 4
int stack[N],sp=0;
void push(int a){
    stack[sp++]=a;
}
int pop(){
    return(stack[--sp]);
}
int main() {
    int i;
    for(i=0;i<N;i++) push(0);
    while(true){
        while((i=pop())==1) if(sp==0) return(0);
        push(1);
        while(sp<N) push(0);
        cout << stack[0] << stack[1] << stack[2] << stack[3] << endl;
    }
    return(0);
}
    使用2進位
    #include <iostream>
using namespace std;
int main() {
    int i;
    for(i=0;i<16;i++){
        cout << (i>>3)%2 << (i>>2)%2 << (i>>1)%2 <<i%2 << endl;
    }
    return(0);
}
    上面程式只是把每樣物品的 0 與 1 列出來，真正計算最大總價值的程式如下：(把藍色字改成如下程式碼)
    假設寶物屬性如下：
    寶物1寶物2寶物3寶物4
    體積3114
    價值4227
    因此全域變數宣告如下：
    int v[4]={3,1,1,4};//寶物體積
    int c[4]={4,2,2,7};//寶物價值
    又假設背包容量 M = 5。
    使用 for 迴圈
    #include <iostream>
using namespace std;

int v[4][2]={{0,3},{0,1},{0,1},{0,4}};//寶物0~3體積 
//v[n][0]表示寶物n不選擇，v[n][1]表示寶物1選擇 
int c[4][2]={{0,4},{0,2},{0,2},{0,7}};//寶物0~3價值 
//c[n][0]表示寶物n不選擇的價值，v[n][1]表示寶物1選擇的價值 

int main() {
  int a1,a2,a3,a4,max=0,M=5;
  for(a1=0;a1<=1;a1++){
    for(a2=0;a2<=1;a2++){
      for(a3=0;a3<=1;a3++){
        for(a4=0;a4<=1;a4++){
          
          if(v[0][a1]+v[1][a2]+v[2][a3]+v[3][a4]<=M)
            if(c[0][a1]+c[1][a2]+c[2][a3]+c[3][a4]>max)
              max=c[0][a1]+c[1][a2]+c[2][a3]+c[3][a4];
          
        }
      }
    }	
  }
  cout << max << endl;
return(0);
    使用堆疊
    #include <iostream>
#define N 4
int stack[N],sp=0;
void push(int a){
  stack[sp++]=a;
}
int pop(){
  return(stack[--sp]);
}

int v[N][2]={{0,3},{0,1},{0,1},{0,4}};//寶物0~3體積 
//v[n][0]表示寶物n不選擇，v[n][1]表示寶物1選擇 
int c[N][2]={{0,4},{0,2},{0,2},{0,7}};//寶物0~3價值 
//c[n][0]表示寶物n不選擇的價值，v[n][1]表示寶物1選擇的價值 

int main() {
  int i,s,t,max=0,M=5;
  for(i=0;i<N;i++) push(0);
  while(true){
    while((i=pop())==1) if(sp==0) {
      cout << max << endl;
      return(0);
    }
    push(1);
    while(sp<N) push(0);
    
    for(s=i=0;i<N;i++) s+=v[i][stack[i]];//計算選擇寶物的重量 
    if(s<=M){
      for(t=i=0;i<N;i++) t+=c[i][stack[i]];//計算選擇寶物的價值 
      if(t>max) max=t;
    }
    
  }
  return(0);
}
    使用2進位
    #include <iostream>
using namespace std;

int v[4][2]={{0,3},{0,1},{0,1},{0,4}};//寶物0~3體積 
//v[n][0]表示寶物n不選擇，v[n][1]表示寶物1選擇 
int c[4][2]={{0,4},{0,2},{0,2},{0,7}};//寶物0~3價值 
//c[n][0]表示寶物n不選擇的價值，v[n][1]表示寶物1選擇的價值 

int main() {
  int i,max=0,M=5;
  for(i=0;i<16;i++){ //選取的寶物種量小於等於背包 
    if(v[3][(i>>3)%2]+v[2][(i>>2)%2]+v[1][(i>>1)%2]+v[0][i%2]<=M)
      if(max<c[3][(i>>3)%2]+c[2][(i>>2)%2]+c[1][(i>>1)%2]+c[0][i%2])
        max=c[3][(i>>3)%2]+c[2][(i>>2)%2]+c[1][(i>>1)%2]+c[0][i%2];
  }
  cout << max << endl;
  return(0);
}

    效率優化：
    上面暴搜會有效率問題，寶物會反覆計算拿與不拿的總價值，因此若能將已經計算過的總價值，使用陣列儲存起來，每當要重算寶物價值時，即可取出陣列內容，減少運算時間。
    下面是手算推演，橫向為背包的容積大小，縱向為寶物編號。
    ppt 說明

  4. 動態規劃法：
  5. 動態規劃法：(記憶體優化)