01背包问题

算法1 （优化空间复杂度类型）

#include<bits/stdc++.h>

using namespace std;

const int N = 1010 ;

int f[N];

int vv[N];    //记录当前商品体积
int w[N];     //记录当前商品价值

int main()
{
    int n , v ;
    cin >> n >> v ;
    for(int i = 1 ; i <= n ; i ++) cin >> vv[i] >> w[i] ;
    for(int i = 1 ; i <= n ; i ++)
    {
        for(int j = v ; j >= vv[i] ; j -- )
        {
            f[j] = max(f[j] , f[j - vv[i]] + w[i]);  // 仔细思考减少空间复杂度，从而为优化为一维
        }
    }
    cout << f[v] << endl ;
}

时间复杂度

参考文献

C++ 代码

blablabla

算法2

(暴力枚举) $O(n^2)$

blablabla

时间复杂度

参考文献

C++ 代码

blablabla