01背包问题

---

题目： 有限个数的货物，具有不同的体积还有价值，怎么让其放进有限体积的背包并价值最大。

货物只有两种可能，放进去/不放进去，本质上其实就是个1/0二叉树。
利用递归的栈效应根据DFS进行先判断后遍历即可。

NOIP版解法没有使用DFS：http://www.wutianqi.com/?p=539

通过建立数组a[i][j],i表示第几件商品，就表示现在所分配的体积（前i-1件商品可以不全占留一点缝但必须是局部最优组合）。
默认采用 i-1 的组合，但是如果同V条件下添加 i （当然会挤掉一部分物体）可以使总的 value 上升则替换 F[i][j] = F[i - 1][j - C[i]] + W[i];（记得先执行C[i]-j检查是否可以容纳商品i），被替换的原物品在F[i-1][j-C[i]]中已经剔除了。

物品号i    1   2   3   4   5   6
体积C 2   3   1   4   6   5
价值W 5   6   5   1   19  7

最大价值 30

物品数量 总体积
物品体积 物品价值

6 10
2 5
3 6
1 5
4 1
6 19
5 7

#include <bits/stdc++.h>
using namespace std;
int main(){
  int i,j,number,volumn;
  scanf("%d %d",&number,&volumn);

  int weight[100]; //记录每个物品的质量
  int value[100];  //记录每个物品的价值
  int v;
  int f[100][100]; // 记录value的数组

  for(i=1;i<number+1;i++){
    scanf("%d",&v);
    value[i]=v;
  }

  for(i=1;i<number+1;i++){
    scanf("%d",&v);
    weight[i]=v;
  }

  for(i=1;i<=number;i++){
    for(j=0;j<=volumn;j++){
      f[i][j]=f[i-1][j];
      if(weight[i]<=j&&f[i-1][j-weight[i]]+value[i]>f[i][j]){
        f[i][j]=f[i-1][j-weight[i]]+value[i];
      }
    }
  }

  cout<<"打印f数组:"<<endl;
  for(i=1;i<=number;i++){
    for(j=0;j<=volumn;j++){
        cout<<f[i][j]<<"\t";
    }
    cout<<endl;
  }
  cout<<endl;


  cout<<"打印选中的节点:"<<endl;
  // 从最大值按照选值规则一路回退即可。
  j=volumn;
  bool x[100];
  for(i=0;i<=volumn;i++){
    f[0][i]=0;
  }
  for(i=number;i>0;i--){
    if(f[i][j]==f[i-1][j]){
        x[i]=false;
    }
    else{
        x[i]=true;
        j=j-weight[i];
    }
  }

  for(i=1;i<=number;i++){
    cout<<x[i]<<"\t";
  }
  cout<<endl;
  cout<<"最优值:"<<f[number][volumn];
}

image.png

如果不想用DFS而想用更加精简的，可以采用一维数组的方法：

• 转移方程：f[v]=max{f[v],f[v-c[i]]+w[i]};

#include <bits/stdc++.h>
using namespace std;
int main(){
      int i,j,number,volumn;
      scanf("%d %d",&number,&volumn);

      int weight[100];
      int value[100];
      int v;
      int f[100];
      bool path[100][100]={false};
      for(i=0;i<100;i++){
        f[i]=0;
      }

      for(i=1;i<number+1;i++){
        scanf("%d",&v);
        value[i]=v;
      }

      for(i=1;i<number+1;i++){
        scanf("%d",&v);
        weight[i]=v;
      }

      for(i=1;i<=number;i++){
        // 从后往前写，因为从前往后，j-1不是之前j-1次操作的解而是被覆盖后的j操作的解。
        for(j=volumn;j>=0;j--){
          if(weight[i]<=j){      // 因为一维数组的原因所以可以不用f[j]=f[j-1];因为不动就是默认f[j-1];
            if(f[j-weight[i]]+value[i]>f[j]){
                path[i][j]=true;
                f[j]=f[j-weight[i]]+value[i];
                // f[j]=max(f[j-weight[i]]+value[i],f[j]);  如果不需要打印路径的话
            }
          }
        }
      }
    cout<<endl;
    cout<<"max="<<f[volumn]<<endl;
    cout<<endl;

    cout<<"打印路径(反方向打印): 因为从头开始的话，它无法知道i+1的volmn应该是哪个-->既可以是平移不变也可以是+=weight[i+1]"<<endl;
    for(i=number;i>0;i--){
        // 之前做了path标记的位置就是选中商品的位置
        if(path[i][volumn]==true){
            cout<<1<<"\t";
            volumn-=weight[i];
        }
        else{
            cout<<0<<"\t";
        }
    }
    cout<<"还剩下"<<volumn<<"的空间还没被利用。"<<endl;
}

沿着x/y轴方向单调上升：

image.png image.png