算法基础之01背包问题

01背包问题

• 核心思想：

  • 二维数组普通写法:

    •   #include<iostream>#include<cstring>#include<algorithm>using namespace std;const int N = 1010;int f[N][N];  //存 i个物品 容量不超过j 的总价值int v[N],w[N];int n,m;int main(){cin>>n>>m;for(int i =1;i<=n;i++) scanf("%d%d" , &v[i] , &w[i]);for(int i=1;i<=n;i++){for(int j=0;j<=m;j++){f[i][j] = f[i-1][j];  //不放第i个物品的情况if(j >= v[i])  //可以放的情况{  f[i][j] = max(f[i][j] , f[i-1][j-v[i]] + w[i]);  //f[i-1]是前一个的状态 +w[i] 是现在的}}}cout<<f[n][m];  //含义: 个数不超过n 容量不超过m 情况下最大价值 return 0;}
      

  • 一维数组优化版本：

    •   int main(){cin>>n>>m;for(int i =1;i<=n;i++) scanf("%d%d" , &v[i] , &w[i]);for(int i=1;i<=n;i++){for(int j=m;j>=v[i];j--)  //逆序遍历 因为原来是用i-1更新i 逆序可以保证//用j-v[i]时 还是上一层(i-1)的 因为j> j-v[i]{f[j] = max(f[j] , f[j-v[i]] + w[i]);}}cout<<f[m];return 0;}