背包习题

背包习题

建议结合背包九讲（灵魂版）-CSDN博客这篇博客进行学习

278. 数字组合 - （01背包，求方案数）

给出$n$个数字，组合=$m$,求几种组合方式

思路

这个题对应背包九讲（灵魂版）-CSDN博客中的背包问题求方案数知识。

既然和为$m$,我们将把体积看作$m$,结合01背包，这里最优价值，其实就是m.也就是每1体积，价值为1。

所以我们将数组$f$,赋值f[0]=1,其余=0.为了保证结果是由0递推得出。

因为01背包不同物品的单位体积价值不同，所以需要int t=max(dp[j],dp[j-v[i]]+w[i])进行比较得出更优。

而这里选择哪个效果都是一样的，只要能组合成$m$.所以这个题不需要比较。直接用$f[j]+=f[j-v]$

也就是更新累加体积为$j$时选择该物品的方案数

代码

#include<bits/stdc++.h>
#define fir(i,a,b) for(int i=a;i<=b;i++)
using namespace std;
int n,m,a[105],f[10500];
int main()
{cin>>n>>m;f[0]=1;for(int i=1;i<=n;i++)cin>>a[i];fir(i,1,n){for(int j=m;j>=a[i];j--)f[j]+=f[j-a[i]];}cout<<f[m]<<'\n';
}

279. 自然数拆分 - （完全背包，求方案数）

将数字拆分为至少两个正整数相加，求方案数，对结果取模

思路

题目标签是完全背包，再结合求方案数问题，根据上一题代码略加修改即可。

我们需要将**$j$循环变成正序**，即每个数字可以重复考虑，这是完全和01区别。

那$i$循环怎么写？
它表示的是选择的数字，我们选择数字的范围是**[1,m-1]**。

记得开long long，取模

代码

#include<bits/stdc++.h>
#define fir(i,a,b) for(int i=a;i<=b;i++)
#define int long long
using namespace std;
int n,m,f[10500];
signed main()
{cin>>m;f[0]=1;fir(i,1,m-1){for(int j=i;j<=m;j++){f[j]+=f[j-i];f[j]%=2147483648; }}cout<<f[m]%2147483648<<'\n';
}

P1060 （01 背包）

给定总钱数$n$，物品总数$m$.再$n$范围内，使得$价值v\ast 重要程度w$最大。

思路

显而易见的01背包

代码

int dp[30050],v[30],p[30];
signed main()
{IOSint n,m;cin>>n>>m;fir(i,1,m){cin>>v[i]>>p[i];for(int j=n;j>=v[i];j--){dp[j]=max(dp[j],dp[j-v[i]]+v[i]*p[i]);}}cout<<dp[n]<<'\n';return 0;
}

P1757 ( 分组背包 )

思路

和模板题区别就是，需要开个容器去分类存放物品。之后三个循环，进行状态转移。

代码

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define IOS ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
#define fir(i,a,b) for(int i=a;i<=b;i++)
#define PII pair<int,int> 
#define fi first
#define se second
const int N=1e3+10;
map<int,vector<PII> > v;
int dp[N];
signed main()
{IOSint n,m;cin>>m>>n;fir(i,1,n){   int a,b,c;cin>>a>>b>>c;v[c].push_back({a,b});}for(auto it:v){  for(int j=m;j>=1;j--){   for(auto ww:it.se){    int v= ww.fi,w=ww.se; if(j>=v)dp[j]=max(dp[j],dp[j-v]+w);}}}cout<<dp[m]<<'\n';
}

280. 陪审团 - (二维费用，求具体方案)

思路

既要满足m个，还要差值最小，再找到和最大，且求具体方案

为了解决这些问题，

• 我们需要初始化为负无穷。为了保证所得结果一定是差值最小的，而不是由其他更大差值状态转移所得。
• 差值可正可负，因为是总差值，所以中间阶段不能简单的用绝对值。所以整体+400.用$400+(d[i]-p[i])=400-p[i]+d[i]$表示差值，此时范围是【0，800】
• 因为求具体方案，不能降维，三个循环$i,遍历每一个评分；j,更新选择不同数量1，m;k,遍历所有可能差值$，不断更新dp.
• $dp[i][j][k]$表示考虑前$i$个评分，选取$j$个，差值为$k$时的最大和。

代码

#include<bits/stdc++.h>
using namespace std;
const int N=205;
int dp[N][25][810],p[N],d[N];
int main()
{   int n,m,T=1;while( cin>>n>>m){if(n==0&&m==0) break;memset(dp,128,sizeof(dp));//初始化无穷小dp[0][0][400]=0;//初始化为for(int i=1;i<=n;i++){cin>>p[i]>>d[i];for(int j=0;j<=m;j++){for(int k=0;k<=800;k++){int t=k-p[i]+d[i];dp[i][j][k]=dp[i-1][j][k];if(j-1<0||t<0||t>800) continue;//该状态不可选取dp[i][j][k]=max(dp[i][j][k],dp[i-1][j-1][t]+p[i]+d[i]);}} }int k=0;//找到最小差值while(dp[n][m][400-k]<0&&dp[n][m][400+k]<0) k++;if(dp[n][m][k+400]>dp[n][m][400-k]) k=400+k;else k=400-k;//查询判断入选的人int c=0,i=n,j=m,a[N];while(j){if(dp[i][j][k]==dp[i-1][j][k])  {i--;continue;}a[c++]=i;   k-=(p[i]-d[i]);j--,i--;}   int pp=0,dd=0;for(int i=c-1;i>=0;i--){pp+=p[a[i]];dd+=d[a[i]];}printf("Jury #%d\n",T);printf("Best jury has value %d for prosecution and value %d for defence:\n",pp,dd);for(int i=c-1;i>=0;i--)//题目要求升序！！！cout<<" "<<a[i];  cout<<"\n\n";//两个换行符！！！T++;}
}

281. 硬币 - 多重背包

给定 N种硬币，其中第 i 种硬币的面值为 Ai，共有 Ci 个。

从中选出若干个硬币，把面值相加，若结果为 S，则称“面值 S能被拼成”。

求 1∼M之间能被拼成的面值有多少个。

思路

$i$ 遍历每一个物品，对于每一个物品，用一个数组used存放，该硬币使用了多少次。

对于 j 没组合，$j-a[i]$可组合，且使用次数足够。说明可以组合成功，更新一下。

代码

#include<bits/stdc++.h>
using namespace std;
int c[120],a[120],f[100050],used[110000];//f是bool类型，used存放不同面值下该硬币使用次数
int main()
{int n,m;while(cin>>n>>m,n&&m){for(int i=1;i<=n;i++) cin>>a[i];for(int i=1;i<=n;i++) cin>>c[i];memset(f,0,sizeof(f));//初始化f[0]=1;     //面值为0，初始化为1  for(int i=1;i<=n;i++){    memset(used,0,sizeof used);//对于不同硬币，进行初始化for(int j=a[i];j<=m;j++){if(!f[j]&&f[j-a[i]]&&used[j-a[i]]<c[i])//j没组合成，j-a[i]已组合，硬币i使用次数足够{f[j]=1;//标记可组合used[j]=used[j-a[i]]+1;}}}int ans=0;for(int i=1;i<=m;i++)//计算有多少可组合if(f[i]) ans++;cout<<ans<<'\n';}
}