当前位置：首页 > news >正文

背包dp与数位dp

news 来源：原创 2025/9/21 7:02:22

背包dp

介绍

动态规划实际上就是将复杂问题分解成若干个子问题，并通过子问题的解逐步发展成整体问题的解的算法思想。（我感觉这个解释就跟递归的思想一样）
背包问题分为01背包(物体只能使用一次)，完全背包(物体可以使用无数次)，多重背包问题，混合背包问题、组合背包问题等等。下面将根据模板题来进行说明。

解法：
一、如果装不下当前物品，那么前 n 个物品的最佳组合和前 n - 1 个物品的最佳组合是一样的。
二、如果装得下当前物品。
假设 1: 装当前物品，在给当前物品预留了相应空间的情况下，前 n - 1 个物品的最佳组合加上当前物品的价值就是总价值。
假设 2: 不装当前物品，那么前 n 个物品的最佳组合和前 n - 1 个物品的最佳组合是一样的。
选取假设 1 和假设 2 中较大的价值，为当前最佳组合的价值。

就建一个如下图所示的表，按以上操作推导表中的所有数据。

模板

#include<bits/stdc++.h>using namespace std;const int MaxN=1010;int w[MaxN],v[MaxN];int f[MaxN][MaxN];//表示前i个物品，背包容量为j下的最优解int n,m;void my_solutin(){for(int i=1;i<=n;i++){for(int j=1;j<=m;j++){if(j<v[i]) f[i][j]=f[i-1][j];else f[i][j]=max(f[i-1][j],f[i-1][j-v[i]]+w[i]);cout<<f[i][j]<<" ";}cout<<endl;}cout<<f[n][m];}int main(){cin>>n>>m;for(int i=1;i<=n;i++) cin>>v[i]>>w[i]my_solutin();return 0;}

用一维数组来完成：

我们在计算第i个物品时，只依靠与i-1这个物品的状态，所以不必追踪每一个物品的清晰状态，在这种条件下，他的时间复杂度就变成了O(n*m)；
外层循环 (i)：遍历每一个物品。物品的索引从 1 到 n。
内层循环 (j)：遍历背包的容量，从 m 到 v[i]。之所以是从大到小遍历，而不是从小到大，是为了避免在同一个物品上多次计算。比如，如果我们从小到大更新 f[j]，在更新 f[j] 时，如果使用了 f[j-v[i]]，它可能会在计算过程中被覆盖，导致错误。
状态转移：
f[j] = max(f[j], f[j-v[i]] + w[i]);：
f[j]表示背包容量为j时的最大价值。
f[j-v[i]]表示背包容量为j-v[i]时的最大价值，即考虑放入第 i 个物品后，剩余的背包容量的最优解。
f[j-v[i]] + w[i]表示放入第 i 个物品后，背包容量为 j 时的最大价值。我们比较放入与不放入的情况，选择较大的值。

 #include<bits/stdc++.h>using namespace std;const int MaxN=1010;int w[MaxN],v[MaxN];int f[MaxN];// f[j]表示背包容量为j时的最大价值int n,m;void my_solutin(){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;}int main(){cin>>n>>m;for(int i=1;i<=n;i++) cin>>v[i]>>w[i];my_solutin();return 0;}

背包dp例题

时间不超过t的情况随便采什么，就是背包问题

#include<bits/stdc++.h>
using namespace std;
const int MaxN = 1010;
int w[MaxN], v[MaxN];
int f[MaxN];// f[j]表示背包容量为j时的最大价值
int t, m;void fun()
{for (int i = 1; i <= m; i++)for (int j = t; j >= v[i]; j--)f[j] = max(f[j], f[j - v[i]] + w[i]);cout << f[t] << endl;
}
int main()
{cin >> t >> m;for (int i = 1;i <= m;i++) cin >> v[i] >> w[i];fun();return 0;
}

背包问题一半版，只考虑容量，没有价值了

#include<bits/stdc++.h>
using namespace std;
const int MaxN=1010;
const int sss=20010;
int v[MaxN];
long long int f[sss];// f[j]表示背包容量为j时的最大价值
int mv,n;
void my_solutin()
{for(int i = 1; i <= n; i++) for(int j = mv; j >= v[i]; j--) f[j] = max(f[j], f[j-v[i]]+v[i]);cout << mv-f[mv] << endl;
}
signed main()
{cin>>mv>>n;for(int i=1;i<=n;i++) cin>>v[i];my_solutin();return 0;
}

比较有意思的一个题（没有标签我应该想不到可以用背包dp写），m当作体积，f[i][j]中的i可以看作是每一个正整数的序号，而每个序号所代表的正整数值便是他的体积量，这样一来就转化成了01背包问题，即选择体积和为m的最大数量；
首先考虑它的状态表示，f[i][j]表示前i个数，且当前的总和恰好是j的方案。
如果不选这个数，f[i][j]=f[i-1][j];
如果选这个数，f[i][j]=max(f[i-1][j],f[i-1][j-a[i])；
当前状态是f[0][0]，那么我们的目标状态是f[n][m];

 #include<bits/stdc++.h>using namespace std;const int MaxN=10010;int n,m;int a[MaxN];int f[MaxN];void solve(){for(int i=1;i<=n;i++){for(int j=m;j>=a[i];j--){f[j]+=f[j-a[i]];}}cout<<f[m]<<endl;}int main(){f[0]=1;cin>>n>>m;for(int i=1;i<=n;i++) cin>>a[i];solve();return 0;}

数位dp

介绍

数位DP往往都是这样的题型，给定一个闭区间[l,r]，让你求这个区间中满足某种条件的数的总数。数位DP就是换一种暴力枚举的方式，使得新的枚举方式符合DP的性质，然后预处理好即可。

所谓数位DP，就是在数的位上进行DP。这样的话，即便对 1e30 的大数，只需在31个数位上进行运算，显然会很高效。数位DP典型的数位分解思路如下图所示：

所谓数位DP，其实就是优化正常数数的过程。而正常数数的过程，其实就是一个dfs的过程。

数位DP问题可以采用前缀和的思想求解：即在求解过程中使用 [0, R] 的结果减去 [0, L-1] 的结果获得[L, R]的结果。这样做的好处在于只需要考虑区间的上边界即可。
数位DP=dfs+记忆化搜索

模板

#include <bits/stdc++.h>
using namespace std;const int maxn=15;int f[maxn][maxn]; //f[i][j]:一共有i位，且最高位是j的方案数
int L,R;void init() {for(int i=0; i<=9; i++)f[1][i]=1;for(int i=2; i<maxn; i++)for(int j=0; j<=9; j++)for(int k=j; k<=9; k++)f[i][j]+=f[i-1][k];
}int dfs(int n) {if(!n) return 1;vector<int> num;while(n) {num.push_back(n%10);n/=10;}int ans=0;int pre_num=0; //上一位数for(int i=num.size()-1; i>=0; i--) {int tmp=num[i];for(int j=pre_num; j<tmp; j++)ans+=f[i+1][j];if(tmp<pre_num)break;pre_num=tmp;if(!i)ans++;}return ans;
}int main() {init();while(cin>>L>>R)cout<<dfs(R)-dfs(L-1)<<endl;return 0;
}

数位dp例题

数字游戏

题目描述
科协里最近很流行数字游戏。某人命名了一种不降数，这种数字必须满足从左到右个位数字呈现小于等于的关系，如123,446.现在大家决定玩一个游戏，指定一个整数闭区间[a,b]，问这个区间内有多少个不降数。

输入
输入多组测试数据。每组只包含两个数字a和b(1<=a,b<=2^31）

输出
每行给出一个测试数据的答案，即[a,b]之间有多少不降数。

样例输入
1 9
1 19
样例输出
9
18

这题的约束条件是低位数永远大于高位数，所以只要控制当i<pre时continue。

#include<bits/stdc++.h>
using namespace std;
long long int n,m;
int a[20],dp[20][10];//a用来存放数字的每位数
int dfs(int pos,int pre,bool limit)//pre表示pos位数的下一位数的值，例如pos=3表示当前位为百位，则pre表示十位数的值
{if(pos==0)return 1;if(!limit&&dp[pos][pre]!=-1)return dp[pos][pre];int ans=0;int up=limit?a[pos]:9;for(int i=0;i<=up;i++){if(i<pre)continue;ans+=dfs(pos-1,i,i==a[pos]&&limit);//从数字的高位向低位递归，新limit的取值根据原limit和i的取值决定，例如246，当pos表示十位数时，如果原limit=1（百位数=2）并且十位数等于4，那么下一次的搜索就会有限制（个位数上界限制为6）}if(!limit)dp[pos][pre]=ans;return ans;
}int solve(int x)
{int pos=0;//pos用于记录当前位数while(x){a[++pos]=x%10;//pos从1开始表示位数从个位到高位x/=10;//如246在数组中的存放方式是6 4 2}return dfs(pos,0,1);//从数字的最高位开始
}int main()
{while(cin>>n>>m){memset(dp,-1,sizeof(dp));cout<<solve(m)-solve(n-1)<<endl;//减的是n-1不是n，n自身要算进去}return 0;
}

算阶例题

按每头奶牛对最小阳光需求度的大小从大到小排序一遍，然后每次在防晒霜选择固定阳光度最大的防晒霜

#include <bits/stdc++.h>using namespace std;
const int N = 3000;int c, l, ans;struct cow {int a, b;
} a[N];struct spf {int a, b;
} b[N];inline bool cmp(cow x, cow y) {return x.a > y.a;}
inline bool cmp_s(spf x, spf y) {return x.a > y.a;}int main() {
//	freopen("in.txt", "r", stdin);scanf("%d %d", &c, &l);for(int i = 1; i <= c; ++i) scanf("%d %d", &a[i].a, &a[i].b);for(int i = 1; i <= l; ++i) scanf("%d %d", &b[i].a, &b[i].b);sort(a + 1, a + 1 + c, cmp);//按minspf递减的顺序排序 sort(b + 1, b + 1 + l, cmp_s);//按固定防晒度从大到小排序 for(int i = 1; i <= c; ++i)for(int j = 1; j <= l; ++j) {if(b[j].a >= a[i].a && b[j].a <= a[i].b && b[j].b) {ans++;b[j].b--;break;//找到了就直接找下一头奶牛可用的防晒霜 }}printf("%d\n", ans);return 0;
}

背包dp

介绍

模板

背包dp例题

数位dp

介绍

模板

数位dp例题

算阶例题

相关文章：