背包问题基本上都是模板题，重点：弄熟多重背包模板

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;
}