网站不用了怎么办,福建省住房与城乡建设厅网站,护理学院网站建设,在省建设厅网站怎样报建目录
背包问题求具体方案
1. 01 背包问题
题目#xff1a;12. 背包问题求具体方案 - AcWing题库
算法思路#xff1a;
代码实现#xff1a;
2. 多重背包问题
算法思路#xff1a;
3. 完全背包问题
算法思路#xff1a;
代码实现#xff1a; 背包问题第九讲—…目录
背包问题求具体方案
1. 01 背包问题
题目12. 背包问题求具体方案 - AcWing题库
算法思路
代码实现
2. 多重背包问题
算法思路
3. 完全背包问题
算法思路
代码实现 背包问题第九讲——背包问题求具体方案 背包问题是一类经典的组合优化问题通常涉及在限定容量的背包中选择物品以最大化某种价值或利益。问题的一般描述是有一个背包其容量为C有一组物品每个物品有重量w和价值v。目标是选择一些物品放入背包使得它们的总重量不超过背包容量同时总价值最大。 背包问题涉及到了三种基础的背包01背包、多重背包、完全背包我们要根据在这几个背包的基础上去计算在获得最大价值的情况下有几种方案并输出具体的方案是求背包问题方案数的进阶版这个需要打印具体方案了。 背包问题求具体方案
上一篇说了一下背包问题求方案数下面进行深化一点就是求具体方案了。同上一篇这些问题都是在01背包、多重背包、完全背包基础上演化来的求具体方案问题会问你一种具体方案编号序列的字典序最小或者打印所有具体方案一般的问题都是问你第一种。若为第二种问法建议使用C语言的printf进行打印因为打印所有具体方案当数据量很大时会有很多输出使用printf会比cout快一点。根据问题的具体类型常见的背包问题包括
1. 01 背包问题
0-1背包问题是指每个物品只有0跟1两种选择即只能选择放或不放不能分割。给定一组物品每个物品都有自己的重量和价值在不超过背包容量的前提下选择一些物品使得总价值最大。 题目12. 背包问题求具体方案 - AcWing题库 有 N 件物品和一个容量是 V 的背包。每件物品只能使用一次。 第 i 件物品的体积是 vi价值是 wi。 求解将哪些物品装入背包可使这些物品的总体积不超过背包容量且总价值最大。 输出 字典序最小的方案。这里的字典序是指所选物品的编号所构成的序列。物品的编号范围是 1…N。 输入格式 第一行两个整数NV用空格隔开分别表示物品数量和背包容积。 接下来有 N 行每行两个整数 vi,wi用空格隔开分别表示第 i 件物品的体积和价值。 输出格式 输出一行包含若干个用空格隔开的整数表示最优解中所选物品的编号序列且该编号序列的字典序最小。 物品编号范围是 1…N。 数据范围 0N,V≤1000 0vi,wi≤1000 输入样例 4 5
1 2
2 4
3 4
4 6输出样例 1 4 算法思路
题目要求了输出字典序最小所以尽量靠前去尽管有不同的方案所获得最大价值一样但是要考虑字典序最小所以一定要选前面的比如选135和234所获得的价值一样但是要选135所以后面遍历下标从小到大遍历的。上面说明了如果第一个物品属于最优解的一种一定要选它这样问题就转化成了从2~N寻找最优解问题以此类推。 状态定义f[i][j]表示从第i个物品开始到最后一个物品背包容量为j所获得的最大价值 状态转移f[i][j]max(f[i1][j],f[i1][j-v[i]]w[i]) f[i][j]的上一个状态就是从i1转移过来的因为我们定义从第i个物品到最后一个物品第i1个物品到最后一个之间的数量是不是比第i个物品到最后一个物品少。f[i1][j]是不选第i个物品f[i1][j-v[i]]w[i]是选第i个物品。因为我要在所有f[i][j]当中选择一个最大值所以前面我管不管的先初始化为不选往后如果背包容量大于体积那我再看看是选了这个物品总价值是否增大如果增大就更新不增大就保持原来。这样写避免了两重判断最优解会有两个max这样只有一个max其实好好想一想我前面先初始化为不选毫无影响的后面大于体积那我就走if不大那就不选呗那不还是初始化为不选。
最后那一段就是查找最优路径了。首先我先初始为背包容量面对第i个物品时若背包剩余容量大于体积并且从上一个状态转移过来选了第i个物品那它一定是最优解并且是字典序是最小的因为我是正序遍历的。
代码实现
#includeiostream
using namespace std;
int N,V;
int v[1005],w[1005],f[1005][1005];//f[i][j]表示从第i个物品开始到最后一个物品背包容量为j所获得的最大价值
int main(){cinNV;for(int i1;iN;i){cinv[i]w[i];}for(int iN;i1;i--){//逆序取物因为f[i][j]定义从i到最后for(int j0;jV;j){f[i][j]f[i1][j];//先初始化为不选第i个物品if(jv[i]){//如果背包剩余容量大于物品体积f[i][j]max(f[i][j],f[i1][j-v[i]]w[i]);//那就寻找最优解到底是选还是不选所获得总价值更大}}}int jV;for(int i1;iN;i){if(jv[i]f[i][j]f[i1][j-v[i]]w[i]){//如果f[i][j]从f[i1][j-v[i]]w[i]转移过来那路径就一定是最优路径couti ;j-v[i];//选了就减去背包容量方便下次寻找}}return 0;
} 2. 多重背包问题
多重背包问题是指每种物品可以取有限次。给定一组物品每种物品都有自己的重量、价值和一个数量限制在不超过背包容量的前提下选择物品的组合使得总价值最大。
算法思路
多重背包跟01背包解法没有太大的区别无非就是多重背包需要先进行二进制拆分把它拆分成01背包再利用01背包求具体方案的模板进行求解。 3. 完全背包问题
完全背包问题是指每种物品可以无限取用可以理解为无限使用。给定一组物品每种物品都有一个重量和价值在不超过背包容量的前提下选择物品的组合使得总价值最大。
算法思路
完全背包求具体方案可能就让你写第几种物品选择了几种例如第一种物品选择了2个第二种物品选择了0个...这样无非又是动态规划问题。可以看一下下面思路。 定义状态 定义 dp[w] 为当背包容量为 w 时能够取得的最大价值。使用 count[i][w] 来记录当背包容量为 w 时物品 i 被选择了多少个。 状态转移方程 对于每个物品 i如果它的重量 weight[i] 小于等于当前背包容量 w则可以选择该物品。状态转移公式为 dp[w]max(dp[w],dp[w−weight[i]]value[i])dp[w] \max(dp[w], dp[w - weight[i]] value[i])dp[w]max(dp[w],dp[w−weight[i]]value[i])在此过程中需要同时更新 count[i][w] 来记录物品的选择次数。 初始化 当不选择任何物品时dp[0] 0其他状态初始化为 0。 最终结果 dp[W] 为在背包容量 W 时能够取得的最大价值。通过 count 数组可以得出每种物品的选择次数。
代码实现
#include iostream
#include vector
using namespace std;int knapsack(int W, const vectorint weight, const vectorint value, int n) {vectorint dp(W 1, 0);vectorvectorint count(n, vectorint(W 1, 0));// 动态规划求解完全背包问题for (int i 0; i n; i) { // 对每个物品进行处理for (int w weight[i]; w W; w) { // 每个物品可以被多次选择if (dp[w] dp[w - weight[i]] value[i]) {dp[w] dp[w - weight[i]] value[i];count[i][w] count[i][w - weight[i]] 1; // 记录物品i的选择次数}}}// 输出结果cout 最大价值: dp[W] endl;cout 每个物品的选择数量: endl;for (int i 0; i n; i) {cout 物品 i 1 : count[i][W] 个 endl;}return dp[W];
}int main() {int W 10; // 背包容量vectorint weight {2, 3, 4}; // 各个物品的重量vectorint value {3, 4, 5}; // 各个物品的价值int n weight.size();knapsack(W, weight, value, n);return 0;
} 上一篇博客背包九讲——背包问题求方案数-CSDN博客
到现在为止背包九讲问题都更新完了但是学习不可停止哦以后我会分享其他的算法或者再去更新一些知识点和例题欢迎大家关注。笔者水平有限一些地方做的不足的地方和需改善的地方大家可以提出来大家有不明白的地方随时可以私信我互相学习大家一起加油
执笔至此感触彼多全文将至落笔为终感谢大家支持。
