算法基础之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;
        }