2024-03-27竞赛笔记

2024/3/27

去使用ACWing把！

动态规划专题——背包问题

ACW2.01背包问题

#include<bits/stdc++.h>
using namespace std;
int m,n;
int w[114514], v[114514];
int f[2001][2001];
int main(){
	scanf("%d%d",&n, &m);
    for (int i=1; i<=n; i++)
        scanf("%d%d",&w[i],&v[i]); 
    for(int i=0;i<=m;i++)f[0][i]=0;
    for(int i=0;i<=n;i++)f[i][0]=0;
	for (int i=1; i<=n; i++){
        for (int j=m;j>=0;j--){        	
        	if(j<w[i]) f[i][j]=f[i-1][j];
        	else f[i][j]=max(f[i-1][j],f[i-1][j-w[i]]+v[i]);
		}
	}
	printf("%d",f[n][m]);
	return 0;
}