做网站最便宜要多少钱,如何知道一个网站是用什么做的,订阅号 小程序,wordpress 浏览计数1.01背包 有 N 件物品和一个容量是 V 的背包。每件物品只能使用一次。 第 i 件物品的体积是 v[i]#xff0c;价值是 w[i]。 求解将哪些物品装入背包#xff0c;可使这些物品的总体积不超过背包容量#xff0c;且总价值最大。 输出最大价值。 对于01背包问题#xff0c;只有…1.01背包 有 N 件物品和一个容量是 V 的背包。每件物品只能使用一次。 第 i 件物品的体积是 v[i]价值是 w[i]。 求解将哪些物品装入背包可使这些物品的总体积不超过背包容量且总价值最大。 输出最大价值。 对于01背包问题只有选或不选所有选法的集合便是由选的情况和不选的情况组成的
以下为未优化二维做法
#includeiostream
using namespace std;
const int N 1e3 10;
int n, m;
int w[N], v[N];
int f[N][N]; //f[i][j]代表【从前i个物品中选且最大容量为j的要求下的最大价值】
int main() {cin n m;for (int i 1; i n; i) {cin v[i] w[i];}for (int i 1; i n; i) { //枚举n个物品for (int j 1; j m; j) { //枚举m个体积if(j v[i])f[i][j] f[i - 1][j];//如果j的体积甚至不如第i个物品大//那么也没有决策的必要了当前的最优解就是上一层的最优解if (j v[i]) f[i][j] max(f[i-1][j], f[i - 1][j - v[i]] w[i]); //如果体积可以装的下第i个物品那么要进行决策/*首先前者f[i][j]代表状态不变即不选择第i个物品时的{最优解}f[i-1][j-v[i]]w[i]代表的是选择上第i个物品时的{最优解}采用先去掉一个i再加上一个i的价值的算法取max则是从二者中抉择出最优的{最优解}*///此处不能暴力的直接每一层都取最大价值使用贪心算法贪心算法只注重于当前的利益//无法保证背包的容量被充分利用从而无法保证最终得到的结果是最优解//动态规划便是对全局的决策得到最优解}}cout f[n][m];return 0;
}
一下为优化后的一维做法 f[i][j]可以变为f[j]? 题目仅要求最终的f[n][m]结果故讨论选前多少个物品意义不大
如果在原代码上进行修改可以得到
if(j v[i]) f[i][j] f[i-1][j];||\/
if(j v[i]) f[j] f[j];
//为等式故可以直接删除
所以可以直接从v[i]枚举到m
但对于j v[i]时在二维做法上每次第i层的取max都用到了第i-1层即在二维枚举时保持了f[i-1]在使用时是原始数据是没有被更新过的没有被污染的
如枚举一个体积为1的物品时 f[2][3] max(f[1][3] , f[1][2] w[2]); 这时的f[1][2],f[1][3]都是没有被更新过的
而如果一维枚举时如果直接使用升序枚举那么就会导致使用 f[j] 时 f[j] 已经是被污染过的
如枚举一个体积为1的物品时 f[3] max(f[3] , f[2] w[2]); 那么此时f[2]已经在之前的枚举时被更新过了导致了现在进行决策时f[2]已经不是原始数据了
综上一维列举时需要逆序进行这样可以避免小体积被提前更新
#includeiostream
using namespace std;
const int N 1e3 10;int f[N];
int n, m;
int v[N], w[N];int main() {cin n m;for (int i 1; i n; i) {cin v[i] w[i];}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];return 0;
}
2.完全背包 有 N 种物品和一个容量是 V 的背包每种物品都有无限件可用。 第 i 种物品的体积是 v[i]价值是 w[i] 。 求解将哪些物品装入背包可使这些物品的总体积不超过背包容量且总价值最大。 输出最大价值。 完全背包问题中的物品是没有选择多少的限制的故我们可以把集合的组成划分成选1,2,3...k个前i个物品。
用代码实现出来便是这样
#includeiostream
using namespace std;
const int N 1e3 10;int n, m;
int v[N], w[N];
int f[N][N]; //f[i][j]表示从前i种物品中选体积不超过jint main() {cin n m;for (int i 1; i n; i) {cin v[i] w[i];}for (int i 1; i n; i) {for (int j 0; j m; j) {for (int k 0; k * v[i] j; k) { //枚举选择第i种物品的个数 //下面的转移方程可能难以理解但其实真正写出来是//f[i][j] max(f[i-1][j-v[i]*k] w[i]*k) (k 0,1,2...)f[i][j] max(f[i][j], f[i - 1][j - v[i] * k] w[i] * k);}}}cout f[n][m];return 0;
}
那么此问题如何优化 f[i][j] max(f[i-1][j] , f[i-1][j-v[i]] w[i], f[i-1][j-2v[i]] 2w[i] , f[i-1][j-3v[i]] 3w[i], ......)
f[i][j-v[i]] max(f[i-1][j-v[i]] , f[i-1][j-2v[i]]w[i], f[i-1][j-3v[i]] 2w[i], ......) 通过观察上面两式可以得知f[i][j-v[i]]的每一项都比上面的每一项少了一个w[i]故可得
f[i][j] max(f[i-1][j] , f[i][j-v[i]] w[i])
根据如上推导可得到新的优化后的代码
#includeiostream
using namespace std;
const int N 1e3 10;int n, m;
int v[N], w[N];
int f[N][N]; //f[i][j]表示从前i种物品中选体积不超过jint main() {cin n m;for (int i 1; i n; i) {cin v[i] w[i];}for (int i 1; i n; i) {for (int j 0; j m; j) {if(j v[i]) f[i][j] f[i - 1][j]; //体积不够时不决策if (j v[i]) f[i][j] max(f[i-1][j], f[i][j - v[i]] w[i]); //体积足够时进行决策根据推得的状态转移方程}}cout f[n][m];return 0;
}
这么看是不是和01背包的方程十分相似
完全背包也可以继续优化成一维但是与01背包不同的是枚举体积时不需要变为逆序
回顾如上状态转移方程都是由第i层转移来的而不是i-1层也就是说其正序枚举也是和优化前的状态转移方程式相同的
优化后代码如下
#includeiostream
using namespace std;
const int N 1e3 10;int n, m;
int v[N], w[N];
int f[N]; int main() {cin n m;for (int i 1; i n; i) {cin v[i] w[i];}for (int i 1; i n; i) {for (int j v[i]; j m; j) {f[j] max(f[j], f[j - v[i]] w[i]);}}cout f[m];return 0;
}
当然还可以让价值和体积不用数组存储而是分散在每一步进行输入此处不再给出
3.多重背包
