完全背包

每件物品可以用无限多次，在限定的体积下，求最大价值。

以当前物品选择多少来划分。

需要注意的一点是：

即可得到递推式。

例题：
Acwing 3. 完全背包问题

参考代码：

#include<iostream>
using namespace std;

typedef pair<int,int> PII;

const int N = 1010;

PII a[N];
int f[N][N];

int n,m;

int main(){
    cin>>n>>m;
    for(int i = 1;i <= n;i++){
        int v,w;
        cin>>v>>w;
        a[i] = {v,w};
    }
    
    for(int i = 1;i <= n;i++){
        int v = a[i].first, w = a[i].second;
        for(int j = 1; j <= m;j++){
            f[i][j] = f[i - 1][j];
            //如果没有递推式的优化还需要加一维去枚举选择多少个
            if(j >= v) f[i][j] = max(f[i][j],f[i][j - v] + w);
        }
    }
    
    cout<<f[n][m];
    return 0;
}

优化为1维：

#include<iostream>
using namespace std;

typedef pair<int,int> PII;

const int N = 1010;

PII a[N];
int f[N];//体积为j的最大价值

int n,m;

int main(){
    cin>>n>>m;
    for(int i = 1;i <= n;i++){
        int v,w;
        cin>>v>>w;
        a[i] = {v,w};
    }
    
    for(int i = 1;i <= n;i++){
        int v = a[i].first, w = a[i].second;
        for(int j = v; j <= m;j++){
            //如果没有递推式的优化还需要加一维去枚举选择多少个
            f[j] = max(f[j],f[j - v] + w);
        }
    }
    
    cout<<f[m];
    return 0;
}