蓝桥杯 Day15 动态规划 背包题目
01背包1、小明的背包
标题链接：小明的背包1 - 蓝桥云课
https://i-blog.csdnimg.cn/direct/8f884a02c5ee4f47a6d724c5a0e6d271.png
1、递推（自下而上）
#include<bits/stdc++.h>
using namespace std;
const int N=1e3+10;
int n,v; //物品数目，背包容量
int w,p;
int dp;
int main()
{
cin>>n>>v;
for(int i=1;i<=n;i++)
cin>>w>>p;
for(int i=1;i<=n;i++)
{
for(int j=0;j<=v;j++)
{
if(w>j)
dp = dp;
else
dp= max(dp,dp]+p);
}
}
cout<<dp<<endl;
return 0;
}
2、滚动数组
#include<bits/stdc++.h>
using namespace std;
const int N=1e3+10;
int n,v; //物品数目，背包容量
int w,p;
int dp;
int main()
{
cin>>n>>v;
for(int i=1;i<=n;i++)
cin>>w>>p;
for(int i=1;i<=n;i++)
{
for(int j=v;j>=w;j--)
{
dp=max(dp,dp]+p);
}
}
cout<<dp<<endl;
return 0;
}
01背包方案数（组合数）
2、2022
标题链接： 2022 - 蓝桥云课
https://i-blog.csdnimg.cn/direct/050630d9de0c44c3bb402a10ca89036c.png
答案：
379187662194355221
解题思路：本题是求解01背包的方案数。可以看作01背包，向背包中装入10个物品，每种物品只有一个，每个物品的体积是1~2022，背包容量是2022。
1、非滚动数组
由于物品体积不确定，我们多界说一维，界说 dp 表示从数字1~i中取j个数和为k的方案数，然后进行分析。
（1）k>=i，即背包容量>=物品体积。那么i可以取，也可以不取。
①取i。从1~i中取 j-1个数，再取i，等价于 dp
②不取i。从1~i中取 j个数，等价于dp
此时的方案数应该为两种情况之和，即dp = dp + dp
（2）k<i，即背包容量<物品体积。取不了i
dp = dp
#include<bits/stdc++.h>
using namespace std;
const int N=3e3;
//dp:表示从数字 1~i里面取 j个数，和为 k的方案数
long long dp={0};
int main()
{
//初始化dp,注意 i 从0开始
for(int i=0;i<=2022;i++)
{
dp=1;
}
//物品体积是1~2022
for(int i=1;i<=2022;i++)
{
//物品
for(int j=1;j<=10;j++)
{
//背包容量
for(int k=1;k<=2022;k++)
{
//i不能取
if(i>k)
dp=dp;
//i可以取
else
//方案数 = 不取 i的方案数 + 取 i的方案数
dp=dp+dp;
}
}
}
cout<<dp;
return 0;
}
2、滚动数组
dp：将 k 拆分成 j 个不同正整数的方案数。
留意：如果从小到大遍历 j，那么在更新 dp 时, dp 大概已经被更新过，导致重复盘算。倒序遍历可以确保每次更新dp 时，dp 是基于之前的状态，而不是当前循环中已经更新过的状态。
#include<bits/stdc++.h>
using namespace std;
const int N=3e3;
long long dp={0};
int main()
{
//初始化 :表示选择0个数，和为0的方案数为1
dp=1;
for(int i=1;i<=2022;i++)
{
//注意j从大到小取
for(int j=10;j>=1;j--)
{
for(int k=i;k<=2022;k++)
{
dp += dp;
}
}
}
cout<<dp;
return 0;
}
3、优化
dp：将 i 拆分为 j 个不同正整数的方案数。我们可以将题目分为两种情况：
（1）j 个数都大于等于 2。
此时，将每个数减 1，得到 j 个新的数（仍互不相同且 >=1），它们的和为 i - j 。对应的方案数为 dp。
（2）j个数里面包含数字 1。
剩下的 j-1 个数必须 >=2 且互不相同，它们的和为 i-1 。将这些数减 1，则 j-1个数的和等于(i-1) - (j-1) = i - j。对应的方案数为 dp 。
因此，总方案数为两种情况的叠加：dp = dp (不包含1) + dp (包含1)。
#include <bits/stdc++.h>
using namespace std;
const int N=3e3;
long long dp={1};
int main()
{
for(int i=1; i<=2022;i++)
{
for(int j=1;j<=10;j++)
{
if(i>=j)
dp = dp+dp;
}
}
cout<<dp;
}
完全背包
1、小明的背包
标题链接：小明的背包2 - 蓝桥云课
https://i-blog.csdnimg.cn/direct/00b2923914d54531860c7f083b2c9b89.png
参考：代码随想录
#include<bits/stdc++.h>
using namespace std;
const int N=1e3+10;
int n,v; //物品数目，背包容量
int w,p;
int dp;
int main()
{
cin>>n>>v;
for(int i=1;i<=n;i++)
cin>>w>>p;
for(int i=1;i<=n;i++)
{
for(int j=w;j<=v;j++)
{
dp= max(dp,dp]+p);
}
}
cout<<dp<<endl;
return 0;
}
2、纪念品
标题链接：纪念品 - 蓝桥云课
https://i-blog.csdnimg.cn/direct/b1fd4b98afa846fd9fd73bc32b4753b4.png https://i-blog.csdnimg.cn/direct/4055f4bb4aac457095a87ff2194f43a6.png
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int M=1e4+10;
const int N=1e3+10;
ll t,n,m;
ll a,dp;
int main()
{
cin>>t>>n>>m;
for(int i=1;i<=t;i++)
{
for(int j=1;j<=n;j++)
cin>>a;
}
//天数
for(int i=1;i<=t-1;i++)
{
//每天的利润，采用贪心，今天买明天卖
memset(dp, 0, sizeof(dp));
//物品
for(int j=1;j<=n;j++)
{
//背包容量
for(ll k=a;k<=m;k++)
{
dp=max(dp,dp]+a-a);
}
}
m+=dp;
}
cout<<m<<endl;
return 0;
}
免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。
页:
[1]