先放一个01背包问题👇
01背包问题

---

什么是完全背包

在01背包的基础上,每个物品可以使用无数次。

状态分析

• 对于当前物品，可以选择放进背包，也可以选择不放进背包

状态计算

定义数组f[i][j] => 其含义为前i个物品任选,背包容量为j时候所能得到的最大价值

• 如果选择放 : 那么 f[i][j] = f[i-1][j-v[i]+w[i]
• 如果选择不放 : 那么 f[i][j] = f[i-1][j]

完整代码

#include<iostream>
#include<algorithm>

using namespace std;

const int N =1010;
int v[N],w[N];
int f[N][N];

int main(){
    int n,m;

    cin>>n>>m;

    for(int i=1; i<=n; i++)cin>>v[i]>>w[i];

    for(int i=1; i<=n; i++){
        for(int j=1; j<=m; j++){
        	//枚举当前物品选择的数量
            for(int k=0; k*v[i]<=j; k++){
            	// 注意对比01背包问题,由于我们上一重循环肯定是满足当前选择的物品重量
            	// 小于背包容量,因此👇
                // f[i][j]=f[i-1][j];//所以没必要写这个
                f[i][j]=max(f[i][j],f[i-1][j-v[i]*k]+w[i]*k);
            }
        }
    }
    cout << f[n][m] << endl;

    return 0;
}

优化方案

为什么要优化?因为三重循环的时间复杂度往往会时间超出题目给出的限制

优化思路

f[i][j]=f[i-1][j-v[i]*k]+w[i]*k 当前物品依次选取0个,1个,2个…
我们将其拆开
f[i][j]=f[i-1][j] + f[i-1][j-v[i]]+w[i] + f[i-1][j-2v[i]]+2w[i] + f[i-1][j-3v[i]]+3w[i]....
按照上式的规则再构造一个新等式
f[i][j-v[i]] = f[i-1][j-v[i]] + f[i-1][j-2v[i]+w[i] + f[i-1][j-3v[i]]+2w[i]....

这样，我们就可以省去第三重循环

实现代码

#include<iostream>
#include<algorithm>

using namespace std;

const int N =1010;
int v[N],w[N];
int f[N][N];
int n,m;

int main(){
    cin>>n>>m;

    for(int i=1; i<=n; i++)cin>>v[i]>>w[i];

    for(int i=1; i<=n; i++){
        for(int j=1; j<=m; j++){
            f[i][j]=f[i-1][j];
            if(j>=v[i])f[i][j]=max(f[i-1][j],f[i][j-v[i]]+w[i]);
        }
    }
    cout << f[n][m] << endl;

    return 0;
}

二维转一维

本题跟01背包的二维转一维的遍历背包顺序 恰好相反
从倒序遍历背包又变回了正序遍历背包
为什么?
因为每个物品可以用多次，我们每次使用的数据都必须得是覆盖之后更新的数据
但是我们记完全背包的代码的时候，可以完全结合着01背包来

#include<iostream>
#include<algorithm>

using namespace std;

const int N =1010;
int v[N],w[N];
int f[N];
int n,m;

int main(){
    cin>>n>>m;
    
    for(int i=1; i<=n; i++)cin>>v[i]>>w[i];
    
    for(int i=1; i<=n; i++){
        for(int j=v[i]; j<=m; j++){
            f[j]=max(f[j],f[j-v[i]]+w[i]);
        }
    }
    
    
    cout<<f[m];
    
    return 0;
}

编写本篇文章目的是笔者想以输出的形式进行学习，顺便记录学习点滴🌻
如果本篇文章对你有帮助的话那就再好不过🌹
本篇文章存在多处不足，还望海涵 😇