背包问题基本上都是模板题，重点：弄熟多重背包模板
dp[j]=max(dp[j-v[i]]+w[i],dp[j]) //核心思路代码（一维数组版）
dp[i][j]=max(dp[i-1][j], dp[i-1][j-v[i]]+w[i])//二维数字版
一、 0-1背包
一般输入两个变量：体积（亦或者是重量）v和价值w
初始化好像不是必须的，如果出bug自己又搞不懂是哪里再加上吧
[NOIP2005]采药 登录—专业IT笔试面试备考平台_牛客网
#include <iostream>
#include <vector>
using namespace std;
int dp[1000];
int p[101];
int t[101];
int main() {
int v,n;
cin>>v>>n;
for(int i=0;i<101;i++){
p[i]=0;
t[i]=0;
}
for(int i=0;i<100;i++){
dp[i]=0;
}
for(int i=0;i<n;i++){
cin>>t[i]>>p[i];
}
for(int i=0;i<n;i++){
for(int j=v;j>=t[i];j--){ //注意是大于等于，有等于！这里错过好几次
dp[j]=max(dp[j],dp[j-t[i]]+p[i]);
}
}
cout<<dp[v];
}
P1507 NASA的食物计划NASA的食物计划 - 洛谷
来个二维数组版的例子。
#include <iostream>
#include <vector>
using namespace std;
int dp[500][500];
int h1[401];
int t1[401];
int k1[501];
int main() {
int h,t,n;
cin>>h>>t>>n;
//初始化
for(int i=0;i<400;i++){
h1[i]=0;
t1[i]=0;
}
for(int i=0;i<500;i++){
k1[i]=0;
}
for(int i=0;i<n;i++){
cin>>h1[i]>>t1[i]>>k1[i];
}
for(int i=0;i<n;i++){
for(int j=h;j>=h1[i];j--){
for(int k=t;k>=t1[i] ;k--){
dp[j][k]=max(dp[j][k],dp[j-h1[i]][k-t1[i]]+k1[i]);
}
}
}
cout<<dp[h][t];
}二、 完全背包
一般输入两个变量：体积（亦或者是重量）v和价值w
完全背包的意思就是每个物品可以取无限次，0-1背包是每个物品只能取走一次。
完全背包例题：3. 完全背包问题 - AcWing题库
#include <iostream>
#include <vector>
#include<bits/stdc++.h>
using namespace std;
int dp[1001];
int v1[1001];
int w[1001];
int main() {
int n,v;
cin>>n>>v;
for(int i=0;i<n;i++){
cin>>v1[i]>>w[i];
}
for(int i=0;i<n;i++){
for(int j=v1[i];j<=v;j++){ //差别在这里
dp[j]=max(dp[j],dp[j-v1[i]]+w[i]);
}
}
cout<<dp[v];
}注意：可以看出，0-1背包和完全背包的问题的解决方案差别不大，主要就是在for(int j=v……部分的差别。
三、多重背包问题
一般输入两个变量：体积（亦或者是重量）v、价值w和数量s
背包问题中最难的了，结合了0-1背包和多重背包的特点，简单来说就是某个物品可以取s次，有了次数限制。
常规思路就是拆分成份，重新构成0-1背包问题。
例题4. 多重背包问题 I - AcWing题库
#include <iostream>
#include <vector>
#include<bits/stdc++.h>
using namespace std;
int dp[1001];
int v1[1001];
int w[1001];
int s[1001];
int main() {
int n,v;
cin>>n>>v;
for(int i=0;i<n;i++){
cin>>v1[i]>>w[i]>>s[i];
}
for(int i=0;i<n;i++){
while(s[i]!=0){ //监控数量
for(int j=v;j>=v1[i];j--){ //0-1背包处理
dp[j]=max(dp[j],dp[j-v1[i]]+w[i]);
}
s[i]--;
}
}
cout<<dp[v];
}可以看到，for(int j=v……这部分的处理和0-1背包的处理逻辑一样。就是在外面增加一个while监控数量的变化即可。整体还是在for(int i=0;i<n;i++){框架下。
上述的微小改进只适用于处理小范围数据集，数据集一大（一两千）就会超时，此时就需要改进算法了，参考下题：
数据量大的情况：5. 多重背包问题 II - AcWing题库
二进制优化是基于这样的事实：
任意正整数可以表示为2的幂之和。
利用这一点，我们可以将每种物品的数量拆分成几个二进制的组件，从而将多重背包问题转换为0-1背包问题的多个实例。
二进制拆分挺麻烦的……要加里面，我写了一版有的用例没有过，还需要再背2024年5月6日
#include <bits/stdc++.h>
using namespace std;
int dp[2102];
int v1[2101];
int w[2101];
int s[2001];
int main() {
int n,v;
cin>>n>>v;
for(int i=0;i<n;i++){
cin>>v1[i]>>w[i]>>s[i];
}
for(int i=0;i<n;i++){
if(s[i]*v1[i]>=v){ //份数乘以重量 大于 容量，采取完全背包。
for(int j=v1[i];j<=v;j++){
dp[j]=max(dp[j],dp[j-v1[i]]+w[i]);
}
}else{
// 二进制拆分，处理多重背包问题
for(int k=1;s[i]>0;k=k*2){
if(k>s[i]){// 当拆分块大于剩余数量时，调整k为剩余数量
k=s[i];
}
int totalv=k*v1[i];
int totalw=k*w[i];
for(int j=v;j>=totalv;j--){//0-1背包处理
dp[j]=max(dp[j],dp[j-totalv]+totalw);
}
s[i]=s[i]-k;
}
}
}
cout<<dp[v];
return 0;
}四、分组背包问题
分组背包问题：9. 分组背包问题 - AcWing题库
就是分组，每个组只能取一个背包。（这个模板没背过，下次记得背，2024年5月6日）
#include <bits/stdc++.h>
using namespace std;
int dp[102];
int v1[101];
int w[101];
int main() {
int n,v,z;
cin>>n>>v;
for(int i=0;i<n;i++){
cin>>z;
for(int j=0;j<z;j++){
cin>>v1[j]>>w[j];
}
for(int k=v;k>=0;k--){
for(int j=0;j<z;j++){
if(k>=v1[j]){
dp[k]=max(dp[k],dp[k-v1[j]]+w[j]);
}
}
}
}
cout<<dp[v];
return 0;
}