蓝桥杯练习(背包问题)

蓝桥杯练习(背包问题)一.0-1背包(基础)问题:Bessie去珠宝商店想要买一些魔法宝石

一 . 0-1背包(基础)

问题:

Bessie 去珠宝商店想要买一些魔法宝石。商店里有 n 个宝石,每个宝石的重量为 wi​,幸运值为 vi​。Bessie 的购物车只能装重量之和不超过 m 的商品,现在她想知道如何选择宝石,能让购买的幸运值之和最大。

输入格式

第一行两个整数 n,m,表示宝石的数量和购物车的承重能力。

接下来 n 行,每行两个整数 wi​,vi​,表示每个宝石的重量和幸运值。

「0-1 背包」是较为简单的动态规划问题,也是其余背包问题的基础。动态规划是不断决策求最优解的过程,「0-1 背包」即是不断对第 i 个物品的做出决策,「0-1」正好代表不选与选两种决定。每个物体只能用一次

二维:

#include<bits/stdc++.h>

using namespace std;

const int MAXN=1005;
int v[MAXN];//体积
int w[MAXN];//价值
int f[MAXN][MAXN]; //f[i][j]表示一种状态,即取n个宝石,体积不超过m时的最大幸运值

int main()
{
	int n,m;
	cin>>n>>m;
	for(int i=1; i<=n; i++)
	{
		cin>>v[i]>>w[i];
	}
    //一维遍历物品看要不要拿,二维遍历背包容积,然后在数组中存储该状态下的最优价值,
    //那么在判断下一个物品时就能直接使用该最优解
	for(int i=1; i<=n; i++) //遍历
	{
		for(int j=1; j<=m; j++)
		{
			if(j<v[i])  //装不下,第i个宝石装入后体积超过m
			   f[i][j]=f[i-1][j];  //此时最优值就是i-1宝石时的状态
			else  //可以装入第i个宝石,那么判断是否要装入,装入前和装入后的幸运值取最大值
			   f[i][j]=max(f[i-1][j],f[i-1][j-v[i]]+w[i]);	//此时的f[i - 1][j - v[i]]就是判断该物品之前容积为j-该物品容积的背包所能装的最优解   
		}
	}
	cout<<f[n][m]<<endl;  //输出最终状态
	return 0;
}

一维(由二维等价转换):j表示背包容积,存储最优情况

#include<bits/stdc++.h>

using namespace std;

const int MAXN=1005;
int v[MAXN],w[MAXN];
int f[MAXN];

int main()
{
	int n,m;
	cin>>n>>m;
	for(int i=1; i<=n; i++)
	{
		cin>>v[i]>>w[i];
	}
	for(int i=1; i<=n; i++)
	{
		for(int j=m; j>=v[i]; j--)  //逆序,很重要!!!
		{
			f[j]=max(f[j],f[j-v[i]]+w[i]);
		}
	}
	cout<<f[m]<<endl;
	return 0;
}

优化输入输出

#include<bits/stdc++.h>

using namespace std;

const int MAXN = 1005;
int f[MAXN];  // 

int main() 
{
    int n, m;   
    cin >> n >> m;

    for(int i = 1; i <= n; i++) 
    {
        int v, w;
        cin >> v >> w;      // 边输入边处理
        for(int j = m; j >= v; j--)
            f[j] = max(f[j], f[j - v] + w);
    }

    cout << f[m] << endl;

    return 0;
}

二 . 完全背包问题

和0-1背包问题类似,不过是每个物品由只能用一次变成了能用多次,代码也只有第二维 j 的访问

顺序不一样,二维到一维的简化过程较复杂,这里只写一维的代码

#include<bits/stdc++.h>

using namespace std;

const int N=1005;
int v[N],w[N];
int f[N];

int main()
{
	int n,m;
	cin>>n>>m;
	for(int i=1; i<=n; i++)
	{
		cin>>v[i]>>w[i];
	}
	for(int i=1; i<=n; i++)
	{
		for(int j=v[i]; j<=m; j++) ///不同之处!!!!
		{
			f[j]=max(f[j],f[j-v[i]]+w[i]);
		}
	}
	cout<<f[m];
	return 0;
	
}

参考:AcWing 4. 在?0基础教你这道题目(会了点下赞👍) – AcWingAcWing,题解,在?0基础教你这道题目(会了点下赞👍),https://www.acwing.com/solution/content/19213/

三 . 多重背包

有 N 种物品和一个容量是 V 的背包。

第 i 种物品最多有 si 件,每件体积是 vi,价值是 wi。

求解将哪些物品装入背包,可使物品体积总和不超过背包容量,且价值总和最大。
输出最大价值。

输入格式
第一行两个整数,N,V,用空格隔开,分别表示物品种数和背包容积。

接下来有 N 行,每行三个整数 vi,wi,si,用空格隔开,分别表示第 i 种物品的体积、价值和数量。

可以将其拆成0-1背包,比如将三件第一种物品拆分成一件一件的记录

#include <bits/stdc++.h>
using namespace std;
int a[10005],b[10005],t=0,n,m,dp[10005]={ },w,v,s;
int main()
{
    cin>>n>>m;
    while(n--) //也可以for循环
    {
        cin>>v>>w>>s;
        while(s--)
        {
            a[++t]=v; //将每个重量值放入新数组
            b[t]=w;
        }//把多重背包拆成01背包
    }
    for(int i=1;i<=t;i++)// 这里是小于t,不再是n,现在拆分后是t个物品
    for(int j=m;j>=a[i];j--)
    dp[j]=max(dp[j-a[i]]+b[i],dp[j]);//直接套01背包的板子
    cout<<dp[m]<<endl;
    return 0;
}


参考链接:https://www.acwing.com/solution/content/13873/

今天的文章蓝桥杯练习(背包问题)分享到此就结束了,感谢您的阅读。

版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。
如需转载请保留出处:https://bianchenghao.cn/66380.html

(0)
编程小号编程小号

相关推荐

发表回复

您的电子邮箱地址不会被公开。 必填项已用*标注