1、B站视频链接：E08【模板】背包DP 01背包_哔哩哔哩_bilibili

题目链接：[USACO07DEC] Charm Bracelet S - 洛谷

#include <bits/stdc++.h> 
using namespace std;
const int N=3410,M=13000;
int n,m;
int d[N],w[N],f[N][M];//价值、体积、状态数组 
//f[i][j]=表示前i件物品放入体积为j的背包的最大价值 
int main(){scanf("%d%d",&n,&m);for(int i=1;i<=n;i++)scanf("%d%d",&w[i],&d[i]);for(int i=1;i<=n;i++){//枚举物品for(int j=1;j<=m;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]]+d[i]);}}}printf("%d\n",f[n][m]);return 0;
}

#include <bits/stdc++.h> 
using namespace std;
const int N=3410,M=13000;
int n,m;
int d[N],w[N],f[M];//价值、体积、状态数组 
int main(){scanf("%d%d",&n,&m);for(int i=1;i<=n;i++)scanf("%d%d",&w[i],&d[i]);for(int i=1;i<=n;i++){for(int j=m;j>=w[i];j--){f[j]=max(f[j],f[j-w[i]]+d[i]);}}printf("%d\n",f[m]);return 0;
}

2、经典题目

1、题目链接：[NOIP2005 普及组] 采药 - 洛谷

#include <bits/stdc++.h> 
using namespace std;
const int X=1010,Y=110;
int T,M;
int t[X],v[Y],f[X];
//f[i][j]表示前i株在j时间内的最大价值
int main(){scanf("%d %d",&T,&M);for(int i=1;i<=M;i++)scanf("%d %d",&t[i],&v[i]);for(int i=1;i<=M;i++){//枚举物品for(int j=T;j>=t[i];j--){//枚举时间（体积），因为限制条件是时间f[j]=max(f[j],f[j-t[i]]+v[i]);}}cout<<f[T];return 0;
} 

2、题目链接：[NOIP2001 普及组] 装箱问题 - 洛谷

#include <bits/stdc++.h> 
using namespace std;
int V,n;
int v[35],f[20010];
//f[i][j]表示前i个箱子放入容量为j中的最大值 
int main(){scanf("%d%d",&V,&n);for(int i=1;i<=n;i++)scanf("%d",&v[i]);for(int i=1;i<=n;i++){for(int j=V;j>=v[i];j--){f[j]=max(f[j],f[j-v[i]]+v[i]);}}printf("%d\n",V-f[V]);//总量减去最大值即为最小值 return 0;
}

3、题目链接：[NOIP2006 普及组] 开心的金明 - 洛谷

#include <bits/stdc++.h> 
using namespace std;
int n,m;
int v[30],w[30];//价格与重要度 
int f[30010]; int main(){scanf("%d%d",&m,&n);for(int i=1;i<=n;i++){scanf("%d%d",&v[i],&w[i]);w[i]*=v[i];}for(int i=1;i<=n;i++){//枚举每个物品 for(int j=m;j>=v[i];j--){//枚举价格（体积），限制条件是价格 f[j]=max(f[j],f[j-v[i]]+w[i]);} }printf("%d\n",f[m]);return 0;
}

4\题目链接：[USACO09OCT] Bessie's Weight Problem G - 洛谷