AcWing算法基础课——第五讲 动态规划 之 背包问题

题解：

#include
#define x first
#define y second
using namespace std;
typedef pair PII;
typedef long long LL;
const int N=1e4+10;
const int mod=1e9;
int f[1010];
int main(){
    int n,m;
    cin>>n>>m;
    for(int i=0;i
        int v,w;
        cin>>v>>w;
        for(int j=m;j>=v;j--){
            f[j]=max(f[j],f[j-v]+w);
        }
    }
    cout< 
题目：3. 完全背包问题 

 题解：
 
#include
#define x first
#define y second
using namespace std;
typedef pair PII;
typedef long long LL;
const int N=1e4+10;
const int mod=1e9;
int f[1010];
int main(){
    int n,m;
    cin>>n>>m;
    for(int i=0;i
        int v,w;
        cin>>v>>w;
        for(int j=v;j<=m;j++){
            f[j]=max(f[j],f[j-v]+w);
        }
    }
    cout< 
题目：4. 多重背包问题 I 

 题解：
 
#include
#define x first
#define y second
using namespace std;
typedef pair PII;
typedef long long LL;
const int N=1e4+10;
const int mod=1e9;
int f[1010];
int main(){
    int n,m;
    cin>>n>>m;
    for(int i=0;i
        int v,w,s;
        cin>>v>>w>>s;
        for(int j=0;j
            for(int k=m;k>=v;k--){
                f[k]=max(f[k],f[k-v]+w);
            }
        }
    }
    cout<