✪动态规划-背包问题✪

均采用了一维数组优化——因为每一列的状态只和上一列有关，且列数递减就不会覆盖值 

#include
using namespace std;

int T;	//总共能采药的时间（相当于背包总容量） 
int M;	//草药总数目（相当于物品总数量） 
int w[105];	//采每一种草药花的时间（相当于每件物品的重量）
int v[105];	//每种草药的价值（相当于每件物品的价值）
//标准的01背包——每种物品要么取，要么不取，在不超过T的情况下获得最大价值 
int dp[1005];	//dp[i]代表用时i所能获取的最大价值 

int main(){
	cin>>T>>M;
	for(int i=1;i<=M;i++)
		cin>>w[i]>>v[i];
	
	for(int i=1;i<=M;i++){
		for(int j=T;j>=0;j--){
			if(j>=w[i])
				dp[j]=max(dp[j-w[i]]+v[i],dp[j]);
		}
	}
	
	cout< 
  开心的金明https://www.luogu.com.cn/problem/P1060  
 
 
#include
using namespace std;

int N;	//总钱数 （背包总容量） 
int M;	// 想买物品数 （物品总数）
int v[30];	//每种物品的价格（每种物品的重量）
int p;		//重要度（本题特有的） 
//发现没有熟悉的"物品价值”？
//原来v*p就是“物品价值”~设个val数组 
int val[30]; 
int dp[30001];

int main(){
	cin>>N>>M;
	for(int i=1;i<=M;i++){
		cin>>v[i]>>p;
		val[i]=v[i]*p;
	}
	
	for(int i=1;i<=M;i++){
		for(int j=N;j>=0;j--){
			if(j>v[i])
				dp[j]=max(dp[j-v[i]]+val[i],dp[j]);
		}
	}
	
	cout< 
 
 
 
 
严酷的训练https://www.luogu.com.cn/problem/P2430
 
#include
#include
#include
#include
#include
using namespace std;

int SL,TL;	//学生和老王的水平值
int m,n;	//题目的总数和知识点总数
int time[5010];	//老王做题时间--->学生做题时间就是time[i]*(TL/SL) 
int p[5010],q[5010];//题目所属知识点和对应的奖励值 
int T;		//规定的时间 
//在T时间内，做每道题的时间是time[p[i]],奖励值是q[i] 
int dp[5005];
int main(){
	cin>>SL>>TL;
	cin>>m>>n;
	for(int i=1;i<=n;i++){
			cin>>time[i];
			time[i]*=(TL/SL); //第i个知识点花费时间
	} 
	
	for(int i=1;i<=m;i++)
		cin>>p[i]>>q[i];	//所属知识点和奖励值 
	cin>>T;
	
	for(int i=1;i<=m;i++){
		for(int j=T;j>=0;j--){
			if(j>=time[i])
				dp[j]=max(dp[j],dp[j-time[p[i]]]+q[i]);
		}
	}
	
	cout< 
 
 
 
 
L国的战斗之间谍https://www.luogu.com.cn/problem/P1910 
 
#include
using namespace std;

int N;		//人数 （物品数） 
int M;		//探查间谍 
int X;		//钱（背包容量） 
int A[1005];	//得到的资料数（物品价值） 
int B[1005];	//伪装能力 
int C[1005];	//工资（物品重量） 
int f[1005][1005];	//j工资去雇人的价值 
int ans;

//求能拿到的最大资料（最大价值） 

int main(){
	cin>>N>>M>>X;
	for(int i=1;i<=N;i++)
		cin>>A[i]>>B[i]>>C[i];
		
	for(int i=1;i<=N;i++)
		for(int j=M;j>=B[i];j--)
			for(int k=X;k>=C[i];k--)
				f[j][k]=max(f[j][k],f[j-B[i]][k-C[i]]+A[i]);
	for(int j=M;j>=0;j--)
		for(int k=X;k>=0;k--)
			ans=max(ans,f[j][k]);
	cout<
 
 
 
音量调节https://www.luogu.com.cn/problem/P1877
 
“到达性的01背包” 
 
 
 
 
#include
using namespace std;

int n;				//歌曲数量 
int beginLevel;		//刚开始吉他的音量
int maxLevel;		//最大音量 
int c[1005];		//第i首歌前改变的音量 （改变量） 
int dp[55][1005];	//dp[i][j]代表前i首歌能否到达音量j 

int main(){
	cin>>n>>beginLevel>>maxLevel;
	for(int i=1;i<=n;i++)
		cin>>c[i];
	dp[0][beginLevel]=1; 
	for(int i=1;i<=n;i++){
		for(int j=maxLevel;j>=0;j--){
			if(j-c[i]>=0)
				dp[i][j]=max(dp[i][j],dp[i-1][j-c[i]]);
			if(j+c[i]<=maxLevel)
				dp[i][j]=max(dp[i][j],dp[i-1][j+c[i]]);
		}
	}
	
	for(int i=maxLevel;i>=0;i--){
		if(dp[n][i]==1){
			cout< 
 
 
分组背包 
什么是分组背包？
 
将这些物品划分为K组，每组中的物品互相冲突，最多选一件
 
通天之分组背包https://www.luogu.com.cn/problem/P1757
 
 
#include
using namespace std;

int n,m;	//n件物品重量为m 
int w[1005],v[1005]; 
int x;		//小组号		
int t;		//最大小组编号
int b[1005];	//b[x]  代表第x组的物品个数 
int g[1005][1005];	//g[i][k]代表第i组第k个是该小组第几个物品 
int dp[1005];
 
int main(){
	cin>>m>>n;
	for(int i=1;i<=n;i++){
		cin>>w[i]>>v[i]>>x;		//依次输入重量、价值、组数
		t=max(t,x);		//当前最大组号 
		b[x]++;			//x小组里的物品数+1 
		g[x][b[x]]=i; 
	}
	
	//所有小组 
	for(int i=1;i<=t;i++){
		//背包容量 
		for(int j=m;j>=0;j--){
			for(int k=1;k<=b[i];k++){
				if(j>=w[g[i][k]])
					dp[j]=max(dp[j],dp[j-w[g[i][k]]]+v[g[i][k]]); 
			}
		} 
	} 
	
	cout< 
 小结&模板 
普通01背包：
 
for 从第一个物体到最后一个
    for 背包容量从后向前
 
分组背包：
 
for 第一小组到最后一个小组 
    for 背包容量--
        for 每组的第一个到最后一个