首页 > 代码库 > 【算法设计与分析】7、0/1背包问题,动态规划
【算法设计与分析】7、0/1背包问题,动态规划
/** * 书本:《算法分析与设计》 * 功能:给定n种物品和一个背包,物品i的重量是Wi, 其价值为Vi,问如何选择装入背包的物品,使得装入背包的物品的总价值最大? * 文件:beiBao.cpp * 时间:2014年11月30日19:22:47 * 作者:cutter_point */ #include <iostream> #define SIZEBEIBAO 20 using namespace std; //这个背包问题的最优的子结构是 /* 首先这里一共有m种物品,背包的总容量是W 1、从第n个开始往前面开始计算,初始化第n个 即c[n][j] j是背包的容量,从0开始递增到背包最大的容量w则当j >= w的时候吧第n个的价值加上去就是加上Vn 当0 <= j < w的时候那么低n个不加上去那就是n 2、当考虑第i个的时候i < n,那么就分为 max{ c[i+1][j] , c[i+1][j-Wi]+Vi} 当j >= Wi 就是 m[i+1][j] */ //我们用m(i,j)表示为已经判断好了1:i-1的序列的背包最大价值,并且此时的背包剩余的容量为j,对物品i进行判断 //n是个数,w是背包最大容量,c[n, w]是背包在n个物品下背包大小是w的最优价值,v是每个的价值,wi是每个的重量 int beiBao(int n, int w, int c[SIZEBEIBAO][SIZEBEIBAO], int *v, int *wi) { c[SIZEBEIBAO][SIZEBEIBAO] = { 0 }; //初始化所有的值 //从第n个开始往前面开始计算,初始化第n个 for (int i = 0; i <= w; ++i) //容量重0到w的初始化 { if (i >= wi[n]) //和第n个比较那个重量,只要超过了这个重量那么价值都是Vn { c[n][i] = v[n]; } else { c[n][i] = 0; //背包容量达不到,那么最优的价值只能是0 } } //这里从第n个开始 //物品从第n个往回迭代 /* 2、当考虑第i个的时候i < n,那么就分为 max{ c[i+1][j] , c[i+1][j-Wi]+Vi} 当j >= Wi c[i+1][j-Wi]+Vi 否则就是 m[i+1][j] */ for (int i = n-1; i >= 0; --i) { for (int j = 0; j <= w; ++j) //背包容量从小增加到最大 { if (j >= wi[i]) //当重量达到了这个要求的时候 c[i][j] = c[i + 1][j - wi[i]] + v[i]; //第i个物品加入背包的时候得到的价值 else c[i][j] = c[i + 1][j]; //当第i个不加如背包的时候 } } //最终的最优解就是 return c[1][w]; /* //当物品的数量从1到n的时候 for (int i = 1; i <= n; ++i) { c[i][0] = 0; //对应的0容量的背包的价值最优肯定是0 //不同的重量就会有不同的背包最优价值 for (int wx = 1; wx <= w; ++wx) { //当对应的重量在增加的时候 //这里要判断这个重量是否比背包可以装的容量大,这里物品的数量i的时候 if (wi[i] > wx) c[i][wx] = c[i - 1][wx]; //2、当Wi > W的时候,第i个的总量>总重量的时候 c[n, w]=c[n-1, w] else //3、当n > 0且 Wi <= w的时候 c[n, w]=MAX{ c[n-1, w], c[n-1, w-Wi]+vi } { //比较这两个中最大的那个 int temp = c[i - 1][wx - wi[i]] + v[i]; if (c[i - 1][wx] > temp) c[i][wx] = c[i - 1][wx]; else c[i][wx] = temp; } } } */ } //得到背包问题的向量解 void qiux(int c[SIZEBEIBAO][SIZEBEIBAO], int *x, int *wi, int w, int n) { for (int i = 1; i < n; ++i) //从一个物品到 n个物品 { if (c[i][w] == c[i + 1][w]) x[i] = 0; //如果加了下一个物品但是最优值没变,说明前面那个没有加入到里面 else { x[i] = 1; //如果加了一个物品价值变了,那么说明这个新的物品可以添加到背包里面去 //加入后占用了质量 w -= wi[i]; } } //最后一个物品是否装入看c[n][w]的最后剩余的w是否还够装,由于最后一个c[i][w] == c[i + 1][w]无法判断 x[n] = (c[n][w]) ? 1 : 0; } int main() { int wi[4] = {0, 4, 3, 2}; int v[4] = { 0, 5, 2, 1 }; int n = 3, w = 6; int c[SIZEBEIBAO][SIZEBEIBAO] = { 0 }; int x[SIZEBEIBAO] = { 0 }; cout << "求得最优的价值是:" << endl; cout << beiBao(n, w, c, v, wi); cout << "则向量x是:" << endl; qiux(c, x, wi, w, n); for (int i = 1; i <= n; ++i) cout << x[i] << " "; cout << endl; return 0; }
【算法设计与分析】7、0/1背包问题,动态规划
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。