算法基础之01背包问题

2023-12-23 23:31:06

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;
          }
        

文章来源:https://blog.csdn.net/Pisasama/article/details/135175679
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。