蓝桥杯算法入门_12(背包问题最详解 -- 01 -- 多重 -- 完全 )

核心要点：状态转移方程！二维 --> 一维优化

• 01背包问题
• • 01背包一维优化
• 多重背包问题
• • 多重背包一维优化
• 完全背包问题
• • 完全背包一维优化
• 二进制数-背包优化
• 背包练习题
• • 找零钱问题的方案数 -- 完全背包

01背包问题

背包问题
给定一组物品 ，每种物品都有自己的重量和价值 ，现有一个背包 ，能承受的重量有限 ，在受限制的重量下 ，取若干物品，
使得总价值最大。 这一类的问题称为背包问题。

01背包问题
当前有N件物品和一个容积为V的背包，已知第i件物品的体积是ci，价值是wi
由于每种物品有且仅有一件 ，因此只能选择放或不放 。
现在你需要选出若干件物品，在它们的重量之和不超过V的条件下，使得价值总和尽可能大
对于每个物品是否要装入背包，我们自然可以进行暴力枚举或搜索，但是如果暴力地去做，那么时间复杂度会非常的高
选用动态规划更优 O(V)

设最大价值 dp[i][j]
dp[i][j] = dp[i - 1][j] //不放(不够放了，放不进去取上一次值) j < ci
dp[i][j] = max( dp[i - 1][j] , dp[i - 1][j - ci] + wi ) //放 ci < j < V
要倒着取 ，…
最小剩余空间 = 总空间 - 最大放的值
实际代码操作过程 ，空间从1开始 如有价值3的东西 ，在第三轮才可以放进去
//第一行输入可选物品数量 ，背包总价值
//接下来输入物品价值 物品体积
输入：
5 10
2 1
3 5
2 5
3 4
4 3
输出：
9

#include
using namespace std; 
#include
int dp[21][1010];
int w[21],c[21];int main(){int N,V;cin >> N >> V;for(int i = 1;i <= N;i++){cin >> w[i] >> c[i]; //价值 ，体积 存数组 }for(int i = 1;i <= N;i++){for(int j = 0;j <= V;j++){if(j >= c[i]){dp[i][j] = max( dp[i - 1][j], dp[i - 1][j - c[i] ] + w[i] );}else{//放不下 ，取上一步，不做改变 dp[i][j] = dp[i - 1][j];}}}cout  << dp[N][V] << endl; return 0;
}

01背包一维优化

优化01背包 改成一维数组
实际上，只有当枚举的背包容量 j>= v[i] 时才会更新状态,优化循环到j == v[i]就停止（之后不会再更新了）
减少空间的优化（边输入变输出，w，v放在）
j价值遍历倒着写（剩余容量|可放空间） ，为了保证更新顺序正确 ！！！
保证 j - c[i]的位置在还没有更新的情况下拿来用 ， 保证更新顺序
输入：
5 10
2 1
3 5
2 5
3 4
4 3
输出：
9

#include
using namespace std; 
//const int N = 1010;
int dp[1010];
int w[21],c[21];int main(){int N,V;cin >> N >> V;for(int i = 1;i <= N;i++){cin >> w[i] >> c[i] ; //价值，体积 }for(int i = 1;i <= N;i++){for(int j = V;j >= c[i];j--){  //从大到小判断 dp[j] = max( dp[j - c[i]] + w[i],dp[j]);}//注意因为小于c[i]的肯定放不下，少遍历几次，优化为j剩余容量到c[i]结束}cout  << dp[V] << endl;  //最终只是获得一个最大值  return 0;}

多重背包问题

/*多重背包
有N个物品 ，第i个物品的体积是ci，价值是wi，（区别：每件可以放多个！）每种物品的数量都是有限的，为ni
现有容量为V的背包 ，请你放入若干个物品，在总体积不超过V的情况下，使总价值尽可能大

朴素算法：
把 n[i]个物品逐个拆分 ,则得到 ∑n[i] 个物品（可以看做价值相同的不同位置物品） 。原问题转化为01背包求解 ，时间复杂度是O(V * ∑n)
dp[i][v] = max ( dp[i][v] ,dp[i - 1][v - k * c[i] ] + k* w[i] ); //0 <= k <= n[i]
(01背包问题 实际上是 特殊的完全背包 )
输入：
5 10
2 1 2
3 5 3
2 5 1
3 4 2
4 3 8
输出：
14

#include
using namespace std; 
int dp[21][1010];
int w[21] ,c[21] ,n[21];int main(){int N,V;cin >> N >> V;for(int i = 1;i <= N;i++){cin >> w[i] >> c[i] >> n[i];}for(int i = 1;i <= N;i++){ //遍历物品 for(int j = 0;j <= V;j++){ //遍历体积空间，逐渐增大判断（每一段怎么放 使价值最大 ，不断更新） for(int k = 0;k <= n[i];k++){ //划分n个判断 ， 乘k个 判断总价值 if(j >= c[i] * k){ //剩余的位置有够，可以再放，进行价值比较 ，更新 dp[i][j] = max( dp[i - 1][j - c[i] * k] + w[i] * k, dp[i][j] );  //跟自己的之前状态比（与放之前比） }}}}cout << dp[N][V] << endl; return 0;
}

多重背包一维优化

优化多重背包
优化后的状态转移方程： dp[j] = max ( dp[j] ,dp[j - k * c[i] ] + k * w[i] ) //一维
输入：
5 10
2 1 2
3 5 3
2 5 1
3 4 2
4 3 8
输出：
14

#include
using namespace std; 
int dp[1010];
int w[21],c[21],n[21];int main(){int N,V;cin >> N >> V;for(int i = 1;i <= N;i++){cin >> w[i] >> c[i] >> n[i];}for(int i = 1;i <= N;i++){for(int j =V;j >= 0;j--){for(int k = 0;k <= n[i];k++){if(j >= c[i] * k){ //dp[V]不断等于递归的（把体积减去同时加上价值）最终(j <= c[i] * k)放不下时，//全部变成 k * w[i] 的值，遍历中不断取与之前比，取最大值dp[j] = max ( dp[j - k * c[i] ] + k * w[i] , dp[j]  );  }}}	}cout << dp[V] <<endl;  //拿V的空间去减 ，去分配 ，不断加值 ，取得最大 return 0;
}

完全背包问题

完全背包问题
有N个物品 ，第i个物品的体积是ci，价值是wi，（区别：每件物品数量为无限个 ，但是背包体积是有限的）
现有容量为V的背包 ，请你放入若干个物品，在总体积不超过V的情况下，使总价值尽可能大
由于背包的体积是有限的-- 可以转化为多重背包问题 --进而转化成01背包问题
状态转移方程：
dp[i][v] = max( dp[i - 1][v], max(dp[i - 1][v - c[i]] + w[i] , dp[i - 1][v - c[i] * 2] + w[i] * 2 ) … )

而dp[i][v - c[i]] = max(dp[i - 1][v - c[i]] , dp[i - 1][v - c[i] * 2] + w[i] * 2 ) … )
就是说 ，我们完全可以用dp[i][v - c[i]] 去更新 dp[i][v] ,而不用去枚举k了，转移可以直接变成如下：
if(j >= c[i])
dp[i][j] = max( dp[i - 1][j],dp[i][j - c[i]] + w[i] ); //状态转移方程 !!!
else 不放(放不下) dp[i][j] = dp[i - 1][j]
输入：
5 10
2 1
3 5
2 5
3 4
4 3
输出：
20

#include
using namespace std; 
int dp[21][1010];
int w[21],c[21];    int main(){int N,V;cin >> N >> V;for(int i = 1;i <= N;i++){cin >> w[i] >> c[i];} for(int i = 1;i <= N;i++){for(int j = 0;j <= V;j++){if(j >= c[i]){ //可以放 dp[i][j] = max ( dp[i][j - c[i]] + w[i] ,dp[i - 1][j] ) ;}else{ //放不下 dp[i][j] = dp[i - 1][j];}}}cout  << dp[N][V] << endl;return 0; 
}

完全背包一维优化

完全背包优化 – 一维 （正序！） dp[j - c[i]]的位置才能保证是之前已经被更新过的位置
//写物品种类 ， 背包总体积
//接下来 物品价值 物品体积
输入：
5 10
2 1
3 5
2 5
3 4
4 3
输出：
20

#include
using namespace std; 
int dp[1010];
int w[21],c[21];   //物品价值 w[i] ，物品体积 c[i] int main(){int N,V;cin >> N >> V;for(int i = 1;i <= N;i++){cin >> w[i] >> c[i];}for(int i = 1;i <= N;i++){for(int j = c[i]; j <= V;j++){ //从可用空间c[i]时才可以放，优化可用空间j 从c[i]开始dp[j] = max( dp[j - c[i]] + w[i] ,dp[j]);  //分配空间减体积 ，加对应价值  ，更新最大值 ，不能放会跳出此次循环 }}cout << dp[V] << endl;  //遍历完最后存放最优解 return 0;
}

二进制数-背包优化

二进制数的使用 – 背包优化
用 1 2 4 8 16 32 实际上 可以表示1 到 63 上的任意整数，由于所有数都是2的幂次，每个数都对应一个二进制位，
所以每个二进制位都可以选或不选 ，能组成1 - 63任意整数。

假设第i个物品有n[i]件，我们把它分成若干组，每一组个数分别为 1 2 4 8 … 2^k-1 , n[i] - 2^k + 1
（k为满足 n[i] - ²k +1>0 的最大整数 ）
而每一组物品对应的体积和价值分别为：(c[i],w[i]) , (2c[i],2w[i]) ,(4c[i],4w[i])
… (2^k - 1^ * c[i], ²k - 1 w[i]) , ((n[i] - 2^k + 1 ) c[i], (n[i]2^k - 1) * w[i])
可证明（ n[i] - 2^k + 1 >= 2^k） 可以完全覆盖 0 - n[i]
输入：
5 10
2 1 2
3 5 3
2 5 1
3 4 2
4 3 8
输出：
14

#include
using namespace std; 
int n[110],c[110],w[110];
int nc[1000],nw[1000];  //保存拆分的组的体积和价值 
int dp[5010];void main(){int N,V;cin >> N >> V;for(int i = 1;i <= N;i++){cin >> w[i] >> c[i] >> n[i];}int ncnt = 0; //统计新的物品的个数 //二进制拆分 for(int i = 1;i <= N;i++){int k;//找到最大的 k for(k = 1;n[i] - (1 << k) + 1 > 0;k++){//可以覆盖 0 - n[i] ，用减去 2 * k 再 + 1 的二进制拆  nc[ncnt] = (1 << (k - 1)) * c[i];   //1 << (k - 1) 不考虑溢出的情况下左移 等效乘2 nw[ncnt] = (1 << (k - 1)) * w[i]; //拆 2^k-1^ ，最小拆到0 ncnt++; } k--;//最后一组 nc[ncnt] = (n[i] - (1 << k) + 1) * c[i]; //存放拆分后的物品体积 nw[ncnt] = (n[i] - (1 << k) + 1) * w[i];ncnt++; //拆一次，种类+1 }//01 背包 for(int i = 0;i < ncnt;i++){for(int j = V;j >= nc[i];j--){ //转化为 01背包 ，一维优化倒着写  ，条件为还放得下 dp[j] = max(dp[j], dp[j - nc[i]] + nw[i]);  //用拆分后的物品放入空间（无限个，则遍历所有最小单位数值 ，取最优） }}cout<< dp[V] << endl; return;
}

背包练习题

找零钱问题的方案数 – 完全背包

有面值为1,2,5,10,20,50的钞票，求凑出100元的方案数

思路:等效【已知总体积V = 100 ， 物品体积为c[i] = {1,2,5,10,20,50} 】
dp累加，dp[0] = 1 , ans = dp[V]

#include 
using namespace std;int dp[1010];
int c[21]= {1,2,5,10,20,50};   //已知物品体积 c[i]  ，总体积V  , 求方案数 
int V = 100,N = 6;int main(){dp[0] = 1;//一开始就一种...理解？   --转成行列表格理解，第一行就1可以 for(int i = 1;i <= N;i++){for(int j = c[i - 1]; j <= V;j++){ //从可用空间c[i]时才可以放，优化可用空间j 从c[i]开始dp[j] +=  dp[j - c[i - 1]];  //分配空间减体积 ，加对应价值  ，更新最大值 ，不能放会跳出此次循环 }}cout << dp[V] << endl;  //遍历完最后存放最优解 return 0;
}

更新中…
背包练习题
购物袋 最小剩余体积 V - dp[V]
存钱罐 最少多少钱 状态转移方程取min
平分娃娃 二进制枚举-减少时间复杂度 -不超时
等和的分隔子集 除去重复计算 sum/2
饭卡 01背包
offer 考虑之前都没用拿到 ，取最高概率
整数划分 完全背包 正着来 ，每次加 取模
新年打牌 方案数
猫狗大战 血量接近，个数差一
搭建双塔 建造双塔，高度相同，是否可行，能就输出最大高度 ，否则 “Impossible” 高 低 三个 if 高->高 ， 低 -> 低 ， 低 -> 高

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！