背包问题练习1

P1833 樱花P1833 樱花 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

题解 这是一个混和背包问题，就是多个背包问题混杂到一起，建议将01背包和多重背包的二进制优化写在一起，这样子背包问题就可以简化到多重背包和完全背包。

代码

#include<iostream>
#include<algorithm>
#include<string>
#include<cstring>
#include<map>
#include<vector>
#include<set>
#include<queue>
#include<stack>
#include<cmath>
#include<string>
using namespace std;
typedef long long ll;
constexpr int N = 10100;
int c[N],dp[N],t[N];
void solve(){
	int th1,ts1,th2,ts2,n;
	char cc;
	cin>>th1>>cc>>ts1>>th2>>cc>>ts2>>n;
	int tz = 60*(th2-th1)+ts2-ts1;
	for(int i = 1;i<=n;i++){
		int t0,c0,s;
		cin>>t0>>c0>>s;
		if(s==0){//完全背包
			for(int j = 0;j<=tz;j++) if(j>=t0) dp[j] = max(dp[j],dp[j-t0]+c0);
		}
		else{//多重背包加上01背包写一起
			int cnt = 0;
			int k = 1;
			while(k<=s){
				cnt++;
				t[cnt] = k*t0;
				c[cnt] = k*c0;
				s-=k;
				k*=2;
			}
			if(s){
				cnt++;
				t[cnt] = s*t0;
				c[cnt] = s*c0;
			}
			for(int m = 1;m<=cnt;m++){
				for(int j = tz;j>=0;j--){
					if(j>=t[m]) dp[j] = max(dp[j],dp[j-t[m]]+c[m]);
				}
			}
		}
		
	}
	cout<<dp[tz];
}
int main(){
    ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
	solve();
}

当完全背包和多重背包写一起建议完全背包不要先读入到数组，等到多重背包进行二进制优化，在读入数组好操作。、

P1049 装箱问题(01背包)P1049 [NOIP2001 普及组] 装箱问题 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

代码(简单就不写题解)

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
constexpr int N = 40;
int dp[20010],v[N];
void solve(){
	int v1,n;
	cin>>v1>>n;
	for(int i =1;i<=n;i++){
		cin>>v[i];
	}
	for(int i = 1;i<=n;i++){
		for(int j = v1;j>=0;j--){
			if(j>=v[i])dp[j] = max(dp[j],dp[j-v[i]]+v[i]);
		}
	}
	cout<<v1-dp[v1];
}
int main(){
    ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
	solve();
}

01背包求方案数

就是需要记录到达每一个的时候就要将当前方案数记录下来，其实就是求达到的路线，就是在01背包的基础上加上一个需要记忆路线的数组。首先即得到max(f[j],f[j-v]+w)，如果maxn==f[j]就是说是前一个更好，所以f[j] = maxn然后就是将方案数变成g[j-a]，如果相等的话，就是相当于有两条路，g[j] = (g[j]+g[j-a])就是说这两条路的方案数都要。

//板子
#include<iostream>
using namespace std;
int n,v,a,b,f[1005],g[1005];
int main(){
    cin>>n>>v;
    for(int i=0;i<=v;i++)
        g[i]=1;
    for(int i=1;i<=n;i++){
        cin>>a>>b;//输入废话
        for(int j=v;j>=a;j--){
            int z=f[j-a]+b;//先用一个数存起来f[j-a]+b
            if(f[j]<z){如果f[j]小于它
                f[j]=z;//更新f[j]
                g[j]=g[j-a];//方案数变为g[j-a]
            }
            else if(f[j]==z)//否则如果它们相等
                g[j]=(g[j]+g[j-a])%1000000007;//方案数更新为现在的方案数加上g[j-a]的方案数取模1e9+7
        }
    }
    cout<<g[v];//最后输出最优选法方案数
}

P1164 小A点菜P1164 小A点菜 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

这个就是求方案数,由于只有价值没有体积什么的，所以不要额外再弄一个记录方案的数组，用dp[]数组即可。

#include<bits/stdc++.h>
using namespace std;
int n,m,a[105],f[105][10005]={0};
int main()
{
    cin>>n>>m;
    for(int i=1;i<=n;i++) 
	cin>>a[i];
    for(int i=1;i<=n;i++) 
	{
        for(int j=1;j<=m;j++) 
		{
            if(a[i] == j)
			{
                f[i][j]=f[i-1][j]+1;
            }  
			else 
			if(a[i]>j) 
			{
                f[i][j]=f[i-1][j];
            } 
			else 
			{
                f[i][j]=f[i-1][j]+f[i-1][j-a[i]];
            }
        }
    }
    cout<<f[n][m];
    return 0;
}

P1060 开心的金明(01背包)P1060 [NOIP2006 普及组] 开心的金明 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

题解：就是说价格和重要度相乘，拿到全部的最大值，所以可以一个数组是两个乘机，另外两个就读入，价格就像当于板子里面的体积，然后用01背包即可

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
constexpr int N = 30050;
constexpr int M = 30;
int p[M],v[M],dp[N];
void solve(){
	int m,n;
	cin>>m>>n;
	for(int i = 1;i<=n;i++){
		cin>>v[i]>>p[i];
		p[i] = v[i]*p[i];//相当于乘机
	}
	for(int i = 1;i<=n;i++){
		for(int j = m;j>=0;j--){
			if(j>=v[i]){
				dp[j] = max(dp[j],dp[j-v[i]]+p[i]);
			}
		}
	}
	cout<<dp[m];
}
int main(){
    ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
	solve();
}

P2722P2722 [USACO3.1] 总分 Score Inflation - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

一个板子题，看到可以重复选择就说明是完全背包。

#include<iostream>
#include<algorithm>
#include<string>
#include<cstring>
#include<map>
#include<vector>
#include<set>
#include<queue>
#include<stack>
#include<cmath>
#include<string>
using namespace std;
typedef long long ll;
constexpr int N = 1e4+10;
int t[N],p[N];
int dp[N];
void solve(){
	int m,n;
	cin>>m>>n;
	for(int i = 1;i<=n;i++){
		cin>>p[i]>>t[i];
	}
	for(int i = 1;i<=n;i++){
		for(int j = 0;j<=m;j++){
			if(j>=t[i]){
				dp[j] = max(dp[j],dp[j-t[i]]+p[i]);
			}
		}
	}
	cout<<dp[m];
}
int main(){
    ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
	solve();
}

P1853 投资的最大效益P1853 投资的最大效益 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

题解：这个稍微会有变形，首先是每一年会总数会加也就是代表着他的最后一套的dp循环会进行的上限会增加，而且还要注意的点是每一年的的时候dp数组需要重新清0，因为都是一年之后重新更新，并且每一年资金总额需要重新更新。接着就是完全背包的板子

#include<iostream>
#include<algorithm>
#include<string>
#include<cstring>
#include<map>
#include<vector>
#include<set>
#include<queue>
#include<stack>
#include<cmath>
#include<string>
using namespace std;
typedef long long ll;
constexpr int N = 1e6+10;
constexpr int M = 20;
int a[M],b[M];//投资额,年利息
int dp[N];
void solve(){
	int sum,year,n;
	cin>>sum>>year>>n;
	for(int i = 1;i<=n;i++){
		cin>>a[i]>>b[i];
		a[i]/=1000;
	}

	for(int k = 1;k<=year;k++){
		int t = sum/1000;//总额更新
		memset(dp,0,sizeof(dp));//dp数组清0
		for(int i = 1;i<=n;i++){
			for(int j = 0;j<=t;j++){
				if(j>=a[i]) dp[j] = max(dp[j],dp[j-a[i]]+b[i]);
			}
		}
		sum+=dp[t];//每年的最大值加到总额里面。
	}
	cout<<sum;
}
int main(){
    ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
	solve();
}