标签：背包 int max long 问题物品 dp

01背包

01背包模型

有一个容量为V的背包。商店有n个物品，每个物品有一个价值v与体积w，一个物品只能拿一次，问可以装下物品的最大价值。
有两个状态，拿或者不拿，用搜索要2^n种。

设状态dp[i][j]表示到第i个物品为止，拿的物品总体积为j的情况下的最大价值。我们不关心某个物品有没有被拿，只关心当前体积下的最大价值。

转移方程为dp[i][j]=max(dp[i-1][j] , dp[i-1][j-w]+v)
如果不拿，最大价值为dp[i-1][j]，如果拿了背包容量就会从上一个的j-w变为j就为dp[i-1][j-w]+v，容量减少了w，价值增加了v。
i是由i-1推出，所以j=0时一定要将dp数组初始化为0。

例题

#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N = 105,M=1010;
int dp[N][M];

signed main() {
	ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
	int n,V;
	cin>>n>>V;

	for(int i=1; i<=n; ++i) { //枚举每件物品
		int w, v;
		cin >> w>> v;
		for(int j=0; j<=V; ++j) { //枚举总体积，有选或不选两种状态，只关心当前体积下的最大价值 
			if(j>=w) dp[i][j] = max(dp[i-1][j],dp[i-1][j-w]+v);//j表示背包装的东西的体积，也不全是。。。 
			else dp[i][j]= dp[i-1][j];
		}
	}

	cout<<dp[n][V]<<'\n';
	return 0;
}

01背包优化

再次弱化i也就是第几个物品的意义。视频例
从二维降为一维，从而节省了空间防止了MLT。但不节省时间，还是要两个循环。改为1维后要从后往前更新，避免用更新后的新数据更新新数据。
状态转移公式dp[j]=max(dp[j],dp[j-w]+v)
例题优化

#include <bits/stdc++.h>
using namespace std;
#define int long long
const int M=1010;
int dp[M];

signed main() {
	ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
	int n,V;
	cin>>n>>V;

	for(int i=1; i<=n; ++i) {
		int w, v;
		cin >> w>> v;
		for(int j=V; j>=w; --j) {//j>=w，否则会是一个负数，这里是w还是0要根据具体情况而定
			dp[j]=max(dp[j],dp[j-w]+v);
		}
	}

	cout<<dp[V]<<'\n';
	return 0;
}

例题

背包与魔法

#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N=10005;
int dp[N][2];//分为用了魔法，与一次也不用魔法的状态

signed main() {
	ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
	//有三种状态，不选，选且用魔法，选但不用魔法
	//用一维数组优化，dp[i][j]，i表示重量，j等于0或1，表示用没用魔法
	int n,m,k;
	cin>>n>>m>>k;
	for(int i=1; i<=n; ++i) {
		int v,w;
		cin>>w>>v;
		for(int j=m; j>=0; --j) {
			//以下同时进行 
			if(j>=w) {
				dp[j][0] = max(dp[j][0],dp[j-w][0]+v);//不选，选但不用魔法
				dp[j][1] = max(dp[j][1],dp[j-w][1]+v);//不选，选但不用魔法 
			}
			if(j>=w+k) {
				dp[j][1] = max(dp[j][1],dp[j-w-k][0] + 2*v);
				//不选，选但用魔法 
			}
		}
	}

	cout<<max(dp[m][0],dp[m][1])<<'\n';
	return 0;
}

蓝桥课程抢购

#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N = 1e5+10;

typedef struct corse{
	int a;
	int b;
	int c;
}corse;

int dp[N];
corse num[N];

bool cmp(corse a1,corse b2){
	return a1.b<=b2.b;
}

signed main() {
	ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
	
	int n;cin>>n;
	int maxT=0;
	for(int i=1;i<=n;++i){
		cin>>num[i].a>>num[i].b>>num[i].c;
		maxT = max(maxT,num[i].b);
	}
	
	sort(num+1,num+n+1,cmp);//优先考虑时间短的，因为时间长的可以兼顾时间短的，不用为此增加背包负重 
	
	int ans=0; 
	
	for(int i=1;i<=n;++i){
		for(int j=maxT;j>=num[i].a;--j){
			int temp=dp[j];
			if(j<=num[i].b){
				dp[j]=max(dp[j],dp[j-num[i].a]+num[i].c);
			}
			//if(dp[j]!=temp)j=max(j,num[i].a); //有了上面的排序，就无需此行代码
			//dp考虑放不放，不考虑顺序，但此题与顺序有关所以要先排序
			
			ans = max(dp[j],ans);//不能保证总时间为j（也就是一定选上时间为maxT的课程）的情况下总价值最大
		}
	}
	
	cout<<ans<<'\n';
	return 0;
}

购物策略

#include <bits/stdc++.h>
using namespace std;
#define int long long
//物品价值为t，体积为c 

//选上一件商品后，那么你获得的是此商品的，t加1（它自己）件商品 
int dp[4100];//获得商品数量为j时所需要的钱，而此时的价值就为t的值 
int t[2100], c[2100]; 

signed main(){
	ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
	int n, v = 0;
	cin >> n;
	
	for(int i = 1; i <= n; ++ i){
		cin >> t[i] >> c[i];
		v = max(v, t[i]);
		t[i]++;//变相价值还要加一，因为还有它自己要算在总数里面
	}
	v += n;//加上v后，即为获得商品最大量 
	
	for(int i = 1; i <= v; ++ i)dp[i] = 1e18;//要注意dp[0] = 0，即选0件商品时付的钱为0 
	
	for(int i = 1; i <= n; ++ i){
		//遍历n件商品，选或不选，选的起，选或不选；选不起跳过 
		for(int j = v; j >= t[i]; -- j){//表示获得商品数量为j时要付的金额 
			dp[j] = min(dp[j], dp[j - t[i]] + c[i]);
			//选或不选，由前面的得到后面的，故到dp[0]时得为0，又为min值，所以这点尤为重要 
		}
	}
	int ans = 1e18;
	for(int i = n; i <= v; ++ i){
		ans = min(ans, dp[i]);
	}
	
	cout << ans << '\n';
	return 0;
}

[小兰的神秘礼物](蓝桥杯省赛无忧班（C&C++ 组）第 3 期 - 小兰的神秘礼物 - 蓝桥云课 (lanqiao.cn))

#include <bits/stdc++.h>
using namespace std;
#define int long long

int dp[1100];

signed main(){
	ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
	
	int v,n;
	cin >> v >> n;

	while(n--){
		int x;
		cin >> x;
		for(int j = v; j >= x; --j){
			dp[j] = max(dp[j], dp[j - x] + x);//选了，dp数组加上这一个体积 
		} 
	}
	
	cout << v - dp[v] << '\n';//求出最大的，然后减去得剩余空间 
	
	return 0;
}

完全背包

完全背包模型

完全背包也叫无穷背包，即每种物品有无数个的背包。
借用一维优化后的[[01背包]]，设状态dp[i]表示拿的物品总体积为i的情况下的最大价值。不关心拿了几个，只关心当前体积下的最大价值。
状态转移方程为dp[i] = max(dp[i],dp[i-w]+v)，与[[01背包]]背包不同，现在必须用新数据更新新数据。因为新数据包含了拿这个物品的状态，而当前物品是可以拿无数次的。最后输出dp[V]。

例题

小明的背包2

#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N = 1e3+10;
int dp[N];

signed main() {
	ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
	int n,V;
	cin>>n>>V;

	for(int i=1; i<=n; ++i) {
		int w,v;
		cin>>w>>v;
		for(int j=w; j<=V; ++j) {
			dp[j]=max(dp[j],dp[j-w]+v);
		}
	}
	
	cout<<dp[V]<<'\n';
	return 0;
}

二维费用背包

二维费用背包模型

有一个体积为V的背包，n件物品，每件物品有一个价值v，体积w，重量m，每种物品只有一个问可以装下的物品的最大价值。
这里的物品只有拿与不拿两种状态，但要同时考虑体积与重量限制。只需在[[01背包]]基础上加以改动，将状态转移方程修改为二维，同样倒着跟新。
dp[i][j]表示当前体积为i，重量为j，的情况下所能拿的物品的最大价值。
状态转移方程：dp[i][j] = max(dp[i][j],dp[i-v][j-m]+w)
时间复杂度O(n*v*m)

例题

小蓝的神秘行囊

#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N = 105;
int dp[N][N];

signed main(){
	int n, V, M;
	cin >> n >> V >> M;
	for(int i = 1; i <= n; ++i){
		int v, m, w;
		cin >> v >> m >> w;
		for(int j = V; j >= v; --j){
			for(int k = M; k >= m; --k){
				dp[j][k] = max(dp[j][k], dp[j - v][k - m] + w);
			}
		}
	}
	cout << dp[V][M] << '\n';
	return 0;
}

分组背包

分组背包模型

有一个体积为V的背包，商店有n组物品，每组物品有若干个价值v，体积w，每组物品中至多选一个，问能装下的最大价值。
设状态dp[i][j]表示到第i组为止，体积为j的最大价值，在这里不可以忽略第一维（要从i-1转移过来）。
状态转移方程为：dp[i][j]=max(dp[i][j],dp[i-1][j-w]+v)
在状态转移之前要先做dp[i][j]=dp[i-1][j]（一定要做，即[[01背包]]中的复制，因为状态是由上一组转移过来的）。

例题

#include <bits/stdc++.h>
using namespace std;
const int N = 1000;
int dp[N][N];

int main(){
	int n, V;
	cin >> n >> V;
	for(int i = 1; i <= n; ++i){
		int s;cin >> s;
		for(int j = 0;j <= V; ++j){
			dp[i][j] = dp[i-1][j];//表示这一组一个物品都不拿的情况 
		}
		
		while(s--){
			int w, v;
			cin >> w >> v;
			for(int j = w; j <= V; ++ j){//正着跑倒着跑都一样，因为他是由上一维转移得到 
				dp[i][j] = max(dp[i][j], dp[i - 1][j - w] + v);
			}
		}
	}
	cout << dp[n][V] << '\n';
	return 0;
}

多重背包

多重背包基础模型

有一个体积为V的背包，商店有n种不同物品，不同物品有价值v与体积w，每种物品有s个，问能装下的最大价值。
这里的每种物品只有s+1种状态，即拿0个，1个，2个，……，s个。
基础模型中，多重背包就是将每种物品的s个摊开，变为s种相同的物品，从而退化为[[01背包]]处理。
只需在[[01背包]]基础稍加改动，对每一个物品循环更新s次即可。
时间复杂度为O(nVs)。
例题：
小明的背包

#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N = 205;
int dp[N]; 

signed main(){
	int n, m;
	cin >> n >> m;
	for(int i = 1; i <= n; ++i){
		int w, v, s;cin >> w >> v >> s;
		while(s --){//循环s次
			for(int j = m; j >= w; --j){
				dp[j] = max(dp[j], dp[j - w] + v);
			}x
		}
	}
	cout << dp[m] << '\n';
	return 0;
}

二进制优化模型

多重背包基础模型的时间复杂度为O(nVs)，当s较大时，容易超时。
为解决这一问题，可以在拆分时进行优化，不再拆分成均为1个物品的组，而是每一组物品个数为1，2，4，8……，最后剩下单独一组，一定存在一种方案来表示0~s的所有情况，类似[[倍增]]，可以想象为二进制。例如s=14，将被拆分为s = 1 + 2 + 4 + 7(1，2，8即二进制1011）。即log2(s)组，对拆分后的物品跑一遍[[01背包]]即可，时间复杂度为O(nVlog(s))。
即将1，2，4，7变为价值是w体积为v；价值是2w体积为2v；价值为4w体积为4v；价值为7w体积为7v的4个物品。拆分后跑[[01背包]]。
例子：新一的宝藏搜寻加强版

#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N = 2e6;
int dp[N]; 

signed main(){
	int n, m;
	cin >> n >> m;
	for(int i = 1; i <= n; ++ i){
		int w, v, s;cin >> v >> w >> s;
		for(int k = 1; k <= s; s -= k, k += k){//倍增1248，类似二进制 
			//当k一直递增到超过s的时候 
			for(int j = m; j >= k * v; -- j)dp[j] = max(dp[j], dp[j - k * v] + k * w);
		}
		//s剩余的部分 
		for(int j = m; j >= s * v; -- j)dp[j] = max(dp[j], dp[j - s * v] + s * w); 
	}
	cout << dp[m] << '\n';
	return 0;
}

单调队列优化多重背包

算法概述

N种物品与容量为V的背包，每种物品数量有限，第i件物品体积为v[i]，价值为w[i]，数量为s[i]求解将哪些物品装入背包使得总价值最大。
可以将[[多重背包]]的二进制优化模型中logN部分一并优化掉。

状态转移分析

先设一个二维数组，dp[i][j]表示将前i种物品放入容量为j的背包中所得到的最大价值。
不放物品 i dp[i-1][j]
放k个物品 i dp[i-1][j-k*v] + k*w
dp[i][j]=max(dp[i-1][j],dp[i-1][j-v]+w,dp[i-1][j-2*v]+2*w……dp[i-1][j-k*v]+k*w)
可以回滚掉第一维。
假设容量为m，那么答案为dp[n][m] 或者 dp[m]。

标签：背包,int,max,long,问题,物品,dp
From： https://www.cnblogs.com/breadcheese/p/18105682

背包问题