题意

• n种物品，每种物品有vol和val，背包体积为v，每种物品可以有任意多个，求背包最大价值和背包恰好装满最大价值

思路

• 01背包变种，更新第二维时需要重复更新，改变循环方向即可

AC代码

#include<bits/stdc++.h>
using namespace std;


int vol[1010],val[1010];
int dp1[202020],dp2[202020];
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    int n,v;
    cin >> n >> v ;
    for(int i=1;i<=n;i++) cin >> vol[i] >> val[i] ;
    for(int i=1;i<=n;i++){
        for(int j=vol[i];j<=v;j++){
            dp1[j]=max(dp1[j],dp1[j-vol[i]]+val[i]);
        }
    }    
    cout << dp1[v] << endl;

    memset(dp2,-0x3f3f3f3f,sizeof(dp2));
    dp2[0]=0;
    for(int i=1;i<=n;i++){
        for(int j=vol[i];j<=v;j++){
            dp2[j]=max(dp2[j],dp2[j-vol[i]]+val[i]);
        }
    }    
    cout << max(dp2[v],0) << endl;
    return 0;
}

复杂度

• 完全背包和01背包一样，时间复杂度都是