动态规划/贪心算法----0/1背包问题AND普通背包问题 - javaeye - ITeye博客
博客分类：
两个背包问题都是比较典型的问题,对这两种算法的理解有很好的帮助.
0/1背包问题--
设U = {u1,u2,u3,......ui}(一共有amount数量的物品)是一组准备放入背包中的物品.设背包的容量为size.
定义每个物品都具有两个属性weight和value.
我们要解决的问题就是计算在所选取的物品总重量不超过背包容量size的前提下使所选的物品总价值最大.
程序的设计:
设V[i, j]用来表示从前i项{u1......ui}中取出来的装入体积为j的背包的最大价值.i的范围是从0到amount,j是从0到size.这样的话要计算的值就是V[amount, size].V[0, j]对于所有的j的值都是0,因为这时候的包中没有物品.同时V[i, 0]的值也是0,因为没有物品可以放到size为0的背包里面.
V[i, j] = 0
若i = 0 或 j = 0;
V[i, j] = V[i - 1, j]
若j & ui.(当物品的重量大于背包承重时,就不巴物品放在里面)
V[i, j] = max{V[i - 1, j], V[i - 1, j - ui.weight] + ui.value}
若i & 0并且j &= ui.
现在就可用动态规划的方法运用上面的公式来填表求解了.
#include &stdio.h&
#define W 1000
#define N 1000
typedef struct data
int returnmax(int a, int b)
return (a & b ? a : b);
int KNAPSACK(goods *P, int a, int s)
int V[N][W];
for(i = 0; i & i++)
V[i][0] = 0;
for(j = 0; j & j++)
V[0][j] = 0;
for(i = 1; i &= i++)
for(j = 1; j &= j++)
V[i][j] = V[i - 1][j];
if(P[i].weight &= j)
V[i][j] = returnmax(V[i][j],V[i - 1][j - P[i].weight] + P[i].vaule);
mv = V[a][s];
int main()
int mostvalue,amount,size,i;
goods A[N];
printf("Input how much the goods have: ");
scanf("%d",&amount);
printf("Input the size of the bag: ");
scanf("%d",&size);
printf("Input the data of the goods: ");
for(i = 0; i & i++)
scanf("%d %d",&A[i].vaule,&A[i].weight);
mostvalue = KNAPSACK(A,amount,size);
printf("%d",mostvalue);
优化的问题:
1.由于计算当前行的时候只需要上一行的结果,所以修改一下程序就可以减少使用的空间.
2.如果要输出所选的物品也是可以实现的.
PS:0/1背包问题和普通背包的差别就在于(1)物品是否可以重复选择, (2)物品是否可以只选取部分.
普通背包问题--
参看上面的PS;
程序的设计:
因为可以重复的选取物品,而且可以部分的选取物品,所以背包应该是完全填满的(0/1背包问题背包不一定是满的).
因此可以先计算每个物品的性价比,然后排序,最后按顺序选取,直到背包填满.
#include &stdio.h&
#include &stdlib.h&
#define MAX 100000
typedef struct data
compare(const void *a, const void *b)
return -(int)(((goods *)a)-&average - ((goods *)b)-&average);
long KNAPSACK(goods *A, long amount, long size)
double mv = 0;
long i = 0;
while(size && amount)
if(size &= (A + i)-&weight)
mv += (A + i)-&
size -= (A + i)-&
mv += ((A + i)-&average) *
mvresult = (long)
int main()
goods A[MAX];
long amount, size, i, temp,
printf("Input the amount of the goods and the size of the bags: ");
scanf("%ld %ld", &amount, &size);
printf("Input the weight and value of each goods: ");
for(i = 0; i & i++)
scanf("%ld %ld",&A[i].weight, &A[i].value);
A[i].average = A[i].value / A[i].
qsort(A, amount, sizeof(A[0]), compare);
mostvalue = KNAPSACK(A, amount, size);
printf("The most value is %ld ", mostvalue);
浏览: 1084135 次
来自: 北京
标示对java很陌生！
Java中\是转意字符， 可是你的这句话我没看懂，只要把得到的 ...
可以参考最新的文档：如何在eclipse jee中检出项目并转 ...
，非常好。动态规划之背包问题（一）
我的图书馆
动态规划之背包问题（一）
March 1, 2013
作者：Hawstein出处：声明：本文采用以下协议进行授权：
，转载请注明作者及出处。
一切都要从一则故事说起。
话说有一哥们去森林里玩发现了一堆宝石，他数了数，一共有n个。但他身上能装宝石的就只有一个背包，背包的容量为C。这哥们把n个宝石排成一排并编上号： 0,1,2,…,n-1。第i个宝石对应的体积和价值分别为V[i]和W[i] （擦，目测这哥们是一苦逼程序员）。排好后这哥们开始思考：背包总共也就只能装下体积为C的东西，那我要装下哪些宝石才能让我获得最大的利益呢？
OK，如果是你，你会怎么做？你斩钉截铁的说：动态规划啊！恭喜你，答对了。那么让我们来看看，动态规划中最最最重要的两个概念：状态和状态转移方程在这个问题中分别是什么。
我们要怎样去定义状态呢？这个状态总不能是凭空想象或是从天上掉下来的吧。为了方便说明，让我们先实例化上面的问题。一般遇到n，你就果断地给n赋予一个很小的数，比如n=3。然后设背包容量C=10，三个宝石的体积为5，4，3，对应的价值为20，10，12。对于这个例子，我想智商大于0的人都知道正解应该是把体积为5和3的宝石装到背包里，此时对应的价值是20+12=32。接下来，我们把第三个宝石拿走，同时背包容量减去第三个宝石的体积（因为它是装入背包的宝石之一），于是问题的各参数变为：n=2，C=7，体积｛5，4｝，价值｛20，10｝。好了，现在这个问题的解是什么？我想智商等于0的也解得出了：把体积为5的宝石放入背包（然后剩下体积2，装不下第二个宝石，只能眼睁睁看着它溜走），此时价值为20。这样一来，我们发现，n=3时，放入背包的是0号和2号宝石；当n=2时，我们放入的是0号宝石。这并不是一个偶然，没错，这就是传说中的“全局最优解包含局部最优解”（n=2是n=3情况的一个局部子问题）。绕了那么大的圈子，你可能要问，这都哪跟哪啊？说好的状态呢？说好的状态转移方程呢？别急，它们已经呼之欲出了。
我们再把上面的例子理一下。当n=2时，我们要求的是前2个宝石，装到体积为7的背包里能达到的最大价值；当n=3时，我们要求的是前3个宝石，装到体积为10的背包里能达到的最大价值。有没有发现它们其实是一个句式！OK，让我们形式化地表示一下它们，定义d(i,j)为前i个宝石装到剩余体积为j的背包里能达到的最大价值。那么上面两句话即为：d(2, 7)和d(3, 10)。这样看着真是爽多了，而这两个看着很爽的符号就是我们要找的状态了。即状态d(i,j)表示前i个宝石装到剩余体积为j的背包里能达到的最大价值。上面那么多的文字，用一句话概括就是：根据子问题定义状态！你找到子问题，状态也就浮出水面了。而我们最终要求解的最大价值即为d(n, C)：前n个宝石（0,1,2…,n-1）装入剩余容量为C的背包中的最大价值。状态好不容易找到了，状态转移方程呢？顾名思义，状态转移方程就是描述状态是怎么转移的方程（好废话！）。那么回到例子，d(2, 7)和d(3, 10)是怎么转移的？来，我们来说说2号宝石（记住宝石编号是从0开始的）。从d(2, 7)到d(3, 10)就隔了这个2号宝石。它有两种情况，装或者不装入背包。如果装入，在面对前2个宝石时，背包就只剩下体积7来装它们，而相应的要加上2号宝石的价值12， d(3, 10)=d(2, 10-3)+12=d(2, 7)+12；如果不装入，体积仍为10，价值自然不变了， d(3, 10)=d(2, 10)。记住，d(3, 10)表示的是前3个宝石装入到剩余体积为10 的背包里能达到的最大价值，既然是最大价值，就有d(3, 10)=max{ d(2, 10), d(2, 7)+12 }。好了，这条方程描述了状态d(i, j)的一些关系，没错，它就是状态转移方程了。把它形式化一下：d(i, j)=max{ d(i-1, j), d(i-1,j-V[i-1]) + W[i-1] }。注意讨论前i个宝石装入背包的时候，其实是在考查第i-1个宝石装不装入背包（因为宝石是从0开始编号的）。至此，状态和状态转移方程都已经有了。接下来，直接上代码。
for(int i=0; i&=n; ++i){
for(int j=0; j&=C; ++j){
d[i][j] = i==0 ? 0 : d[i-1][j];
if(j&=V[i-1] && i&0)
d[i][j] &?= d[i-1][j-V[i-1]]+W[i-1];
i=0时，d(i, j)为什么为0呢？因为前0个宝石装入背包就是没东西装入，所以最大价值为0。 if语句里，j&=V[i-1]说明只有当背包剩余体积j大于等于i-1号宝石的体积时，我才考虑把它装进来的情况，不然d[i][j]就直接等于d[i-1][j]。i&0不用说了吧，前0个宝石装入背包的情况是边界，直接等于0，只有i&0才有必要讨论，我是装呢还是不装呢。简单吧，核心算法就这么一丁点，接下来上完整代码knapsack.cpp。
/**0-1 knapsack d(i, j)表示前i个物品装到剩余容量为j的背包中的最大重量**/
#include&cstdio&
using namespace std;
#define MAXN 1000
#define MAXC 100000
int V[MAXN], W[MAXN];
int d[MAXN][MAXC];
int main(){
freopen("data.in", "r", stdin);//重定向输入流
freopen("data.out", "w", stdout);//重定向输出流
while(scanf("%d %d", &n, &C) != EOF){
for(int i=0; i&n; ++i)
scanf("%d %d", &V[i], &W[i]);
for(int i=0; i&=n; ++i){
for(int j=0; j&=C; ++j){
d[i][j] = i==0 ? 0 : d[i-1][j];
if(j&=V[i-1] && i&0)
d[i][j] &?= d[i-1][j-V[i-1]]+W[i-1];
printf("%d\n", d[n][C]);//最终求解的最大价值
fclose(stdin);
fclose(stdout);
其中freopen函数将标准输入流重定向到文件data.in，这比运行程序时一点点手输要方便许多，将标准输出流重定向到data.out。 data.in中每组输入的第一行为宝石数量n及背包体积C，接下来会有n行的数据，每行两个数对应的是宝石的体积及价值。本测试用例data.in如下：5 10
data.out为算法输出结果，对应该测试用例，输出结果如下：19
好，至此我们解决了背包问题中最基本的0/1背包问题。等等，这时你可能要问，我现在只知道背包能装入宝石的最大价值，但我还不知道要往背包里装入哪些宝石啊。嗯，好问题！让我们先定义一个数组x，对于其中的元素为1时表示对应编号的宝石放入背包，为0则不放入。让我们回到上面的例子，对于体积为5，4，3，价值为20，10，12的3个宝石，如何求得其对应的数组x呢？（明显我们目测一下就知道x={1 0 1}，但程序可目测不出来）OK，让我们还是从状态说起。如果我们把2号宝石放入了背包，那么是不是也就意味着，前3个宝石放入背包的最大价值要比前2个宝石放入背包的价值大，即：d(3, 10)&d(2, 10)。再用字母代替具体的数字（不知不觉中我们就用了不完全归纳法哈），当d(i, j)&d(i-1, j)时，x(i-1)=1;OK，上代码：
//输出打印方案
int j = C;
for(int i=n; i&0; --i){
if(d[i][j] & d[i-1][j]){
x[i-1] = 1;
j = j - V[i-1];//装入第i-1个宝石后背包能装入的体积就只剩下j - V[i-1]
for(int i=0; i&n; ++i)
printf("%d ", x[i]);
好了，加入这部分内容，knapsack.cpp变为如下：
/**0-1 knapsack d(i, j)表示前i个物品装到剩余容量为j的背包中的最大重量**/
#include&cstdio&
using namespace std;
#define MAXN 1000
#define MAXC 100000
int V[MAXN], W[MAXN], x[MAXN];
int d[MAXN][MAXC];
int main(){
freopen("data.in", "r", stdin);
freopen("data.out", "w", stdout);
while(scanf("%d %d", &n, &C) != EOF){
for(int i=0; i&n; ++i)
scanf("%d %d", &V[i], &W[i]);
for(int i=0; i&n; ++i)
x[i] = 0; //初始化打印方案
for(int i=0; i&=n; ++i){
for(int j=0; j&=C; ++j){
d[i][j] = i==0 ? 0 : d[i-1][j];
if(j&=V[i-1] && i&0)
d[i][j] &?= d[i-1][j-V[i-1]]+W[i-1];
printf("%d\n", d[n][C]);
//输出打印方案
int j = C;
for(int i=n; i&0; --i){
if(d[i][j] & d[i-1][j]){
x[i-1] = 1;
j = j - V[i-1];
for(int i=0; i&n; ++i)
printf("%d ", x[i]);
printf("\n");
fclose(stdin);
fclose(stdout);
data.out输出结果变为：19
至此，好像该解决的问题都解决了。当一个问题找到一个放心可靠的解决方案后，我们往往就要考虑一下是不是有优化方案了。为了保持代码的简洁，我们暂且把宝石装包方案的求解去掉。该算法的时间复杂度是O(n*C)，即时间都花在两个for循环里了，这个应该是没办法再优化了。再看看空间复杂度，数组d用来保存每个状态的值，空间复杂度为O(n*C)；数组V和W用来保存每个宝石的体积和价值，空间复杂度为O(n)。程序总的空间复杂度为 O(n*C)，这个是可以进一步优化的。首先，我们先把数组V和W去掉，因为它们没有保存的必要，改为一边读入一边计算：
int V = 0, W = 0;
for(int i=0; i&=n; ++i){
if(i&0) scanf("%d %d", &V,&W);
for(int j=0; j&=C;++j){
d[i][j] = i==0 ? 0 : d[i-1][j];
if(j&=V && i&0) d[i][j] &?= d[i-1][j-V]+W;
好了，接下来让我们继续压榨空间复杂度。保存状态值我们开了一个二维数组d，在看过把一维数组V和W变为一个变量后，我们是不是要思考一下，有没有办法将这个二维数组也压榨一下呢？换言之，这个二维数组中的每个状态值我们真的有必要都保存么？让我们先来看一下以下的一张示意图（参照《算法竞赛入门经典》P169的图画的）
由上面那一小段优化过后的代码可知，状态转移方程为：d(i, j)=max{ d(i-1, j), d(i-1, j-V)+W }，也就是在计算d(i, j)时我们用到了d(i-1,j)和d(i-1, j-V)的值。如果我们只用一个一维数组d(0)～d(C)来保存状态值可以么？将i方向的维数去掉，我们可以将原来二维数组表示为一维数据：d(i-1, j-V)变为d(j-V)， d(i-1, j)变为d(j)。当我们要计算d(i, j)时，只需要比较d(j)和d(j-V)+W的大小，用较大的数更新d(j)即可。等等，如果我要计算d(i, j+1)，而它恰好要用到d(i-1, j)的值，那么问题就出来了，因为你刚刚才把它更新为d(i, j)了。那么，怎么办呢？按照j递减的顺序即可避免这种问题。比如，你计算完d(i, j)，接下来要计算的是d(i,j-1)，而它的状态转移方程为d(i, j-1)=max{ d(i-1, j-1), d(i-1, j-1-V)+W }，它不会再用到d(i-1,j)的值！所以，即使该位置的值被更新了也无所谓。好，上代码：
memset(d, 0, sizeof(d));
for(int i=0; i&=n; ++i){
if(i&0) scanf("%d %d", &V,&W);
for(int j=C;j&=0; --j){
if(j&=V && i&0) d[j] &?= d[j-V]+W;
优化后的完整代码如下，此时空间复杂度仅为O(C)。
/**0-1 knapsack d(i, j)表示前i个物品装到剩余容量为j的背包中的最大重量**/
#include&cstdio&
#include&cstdlib&
#include&cstring&
using namespace std;
int main(){
freopen("data.in", "r", stdin);
freopen("data.out", "w", stdout);
int n, C, V = 0, W = 0;
while(scanf("%d %d", &n, &C) != EOF){
int* d = (int*)malloc((C+1)*sizeof(int));
memset(d, 0, (C+1)*sizeof(int));
for(int i=0; i&=n; ++i){
scanf("%d %d", &V, &W);
for(int j=C; j&=0; --j){
if(j&=V && i&0)
d[j] &?= d[j-V]+W;
printf("%d\n", d[C]);
fclose(stdin);
fclose(stdout);
OK，背包问题暂时先讲这么多，以后接着讲。
TA的推荐TA的最新馆藏
喜欢该文的人也喜欢关于求解0/1背包问题的动态规划算法；摘要：本文通过研究动态规划原理，提出了根据该原理；并对算法的正确性作了验证．观察程序运行结果，发现；关键字：动态规划；０／１背包；约束条件；序偶；决；1、引言；科学研究与工程实践中，常常会遇到许多优化问题，而；对于0/1背包问题，我们可以这样描述：设有一确定；0/1背包问题是工程问题的典型概括，怎么样高效求；2、求解问题
关于求解0/1背包问题的动态规划算法
摘要：本文通过研究动态规划原理，提出了根据该原理解决０／１背包问题的方法与算法实现，
并对算法的正确性作了验证．观察程序运行结果，发现基于动态规划的算法能够得到正确的决策方案且比穷举法有效．
关键字：动态规划；０／１背包；约束条件；序偶；决策序列；支配规则
科学研究与工程实践中，常常会遇到许多优化问题，而有这么一类问题，它们的活动过程可以分为若干个阶段，但整个过程受到某一条件的限制。这若干个阶段的不同决策的组合就构成一个完整的决策。0/1背包问题就是一个典型的在资源有限的条件下，追求总的收益最大的资源有效分配的优化问题。
对于0/1背包问题，我们可以这样描述：设有一确定容量为C的包及两个向量C’=（S1，S2，……，Sn）和P=（P1，P2，……，PN），再设X为一整数集合，即X=1，2，3，……，N，X为SI、PI的下标集，T为X的子集，那么问题就是找出满足约束条件∑Si〈=C，使∑PI获得最大的子集T。在实际运用中，S的元素可以是N个经营项目各自所消耗的资源，C可以是所能提供的资源总量，P的元素可是人们从各项项目中得到的利润。
0/1背包问题是工程问题的典型概括，怎么样高效求出最优决策，是人们关心的问题。
2、求解问题的动态规划原理与算法 2．1动态规划原理的描述
求解问题的动态规划有向前处理法向后处理法两种，这里使用向前处理法求解0/1背包问题。对于0/1背包问题，可以通过作出变量X1，X2，……，XN的一个决策序列来得到它的解。而对于变量X的决策就是决定它是取0值还是取1值。假定决策这些X的次序为Xn，XN-1，……，X0。在对X0做出决策之后，问题处于下列两种状态之一：包的剩余容量是M，没任何效益；剩余容量是M-w，效益值增长了P。显然，之后对Xn-1，Xn-2，……，X1的决策相对于决策X所产生的问题状态应该是最优的，否则Xn，……，X1就不可能是最优决策序列。如果设Fj（X）是KNAP（1，j，X）最优解的值，那么Fn（M）就可表示为
FN（M）=max(fn(M),fn-1(M-wn)+pn)}
对于任意的fi(X),这里i&0，则有
fi(X)=max{fi-1(X),fi-1(X-wi)+pi}
为了能由前向后推而最后求解出FN（M），需从F0（X）开始。对于所有的X&=0,有F0（X）=0，当X&0时，有F0（X）等于负无穷。根据（2），可求出0〈X〈W1和X〉=W1情况下F1（X）的值。接着由（2）不断求出F2，F3，……，FN在X相应取值范围内的值。
2．2 0/1背包问题算法的抽象描述
(1)初始化各个元素的重量W[i]、效益值P[i]、包的最大容量M； (2)初始化Ｓ0； (3)生成Si；
a．在中Ｓ找满足约束条件的第R对序偶； b．生成S1
c．清除不满足条件的序偶；
d．将Sn-1中满足条件的序偶复制到Sn 中； （4）对Sn+1置初值；
（5）若不满足循环次数转（3）,否则转（６）； （6）用回溯法确定决策序列；终止程序。 2．3计算复杂性分析
假设Si的序偶是|Ｓi |。在i＞０的情况下，每个Ｓi由Ｓ1i-1和Ｓ1i归并而成，并且｜ii-1
Ｓ1 |&=|Ｓ|,因此｜Ｓ |&=2|Ｓ|。在最坏情况下没有序偶被清除，所以 对|Ｓi|求和(i=0,1,2,．．．n-1)的结果是２n-1,也就是说ＤＫＮＡＰ的空间复杂度为
Ｏ（２）。
由Ｓi-1生成Ｓi需要|Ｓi-1||的时间，所以在计算S0，S1，S2，……，Sn-1时所消耗的总时间为（∑|Ｓi-1|），0〈＝i〈＝n－１。由于｜Ｓi｜〈＝２n，所以计算这些Ｓi总的时间为Ｏ（２n）。
该算法的时间复杂性为Ｏ（２n），似乎表明当Ｎ很大时它的有效性不会让人满意，但由于支配规则的引入，很好的清除了不满足约束的序偶，因而该算法在很多情况下都能在可接受的时间内求出决策序列。 ２．４基于动态规划的算法源程序
由于算法源程序有一定的篇幅，将其附后。
3、性能测试
３．１测试问题
为了验证算法的正确性与有效性，用两个数组Ｐ［Ｎ］和Ｗ［Ｎ］分别存储 始记录Ｃ’和P，记录为用穷举法已求出最优决策的实例。现分别取Ｎ＝3，4 ，6，10进行实验。
3．2试验结果与分析
为了便于说明问题，现将实验过程中的N取不同值的一组向量Ｃ’和P（也就 是重量与效益值）记录如下：
N=3：Ｃ’=（2，3，4）；P=（1，2，5）；M=6； N=4：Ｃ’=（2，4，6，7）；P=（6，10，12，13）；M=11； N=6：Ｃ’=（100，50，20，10，7，3）；P=（90，70，30，20，5，15）；M=165； N=10：Ｃ’=（2，4，5，7，10，14，19，20，25，30）；
P=（1，3，4，5，10，15，20，25，36，28）；M=70； 运行程序，与上述实例对应的决策序列为（1 0 1）、（0 1 0 1）、（1 1 0 1 1）和（0 0 1 1 0 1 1 0 1 0），各决策序列与穷举法得到的结果一致，得到了最大的效益值，都为有限资源下的最优决策序列。
根据程序运行的中间结果，记录上述实例每次的Si的序偶个数，结果如下表：
Si的序偶个数表：
i对于每一个Si并非都是|Si|= =2|Si-1|,尤其当i&4时效果更加明显，减少了搜索的范围，避免了穷举搜索，比穷举法有效．
４，结束语
通过将动态规划原理引入到解０／１背包问题中，由于支配规则的高效性，使该算法比运用穷举思想的算法有效．需要指出的是，由于它的时间复杂性为Ｏ（２n），０／１背包问题是一个ＮＰ－难问题。如果能够将它降为多项式复杂性，那么所有的ＮＰ－难问题就都可以在多项式时间内求解，这将会大大提高现行些类问题的算法的可靠性与效率。在这方面，有待深入研究，也是值得研究的问题。
参考文献：
[1] 数据结构：C语言版/严蔚敏等编著。 [2] Ｃ语言程序设计：潭浩强编著。
[3] 计算机算法基础:第二版/余祥宣等编著。
用动态规划解0/1背包问题的源程序代码：
#include&stdio.h& #include&math.h& #define n 6 void DKNAP(); main() {
int p[n+1],w[n+1];
int M,m=1,i,j;
for(i=1;i&=n;i++)
printf(&\nin put the weight and the p:&);
scanf(&%d %d&,&w[i],&p[i]);
printf(&%d&,m);
printf(&\n in put the max weight M:&);
scanf(&%d&,&M);
DKNAP(p,w,M,m); }
void DKNAP(int p[],int w[],int M,int m) { int p2[m],w2[m],pp,ww,
int F[n+1],pk,q,k,l,h,u,i,j,next,max,s[n+1];
p2[1]=w2[1]=0;
F[1]=next=2;
for(i=1;i&n;i++)
max=0； u=l;
for(q=l;q&=h;q++)
if((w2[q]+w[i]&=M)&&max&=w2[q]+w[i])
max=w2[q]+w[i];
for(j=l;j&=u;j++)
{ pp=p2[j]+p[i];
ww=w2[j]+w[i];
while(k&=h&&w2[k]&ww)
{ p2[next]=p2[k];
w2[next]=w2[k];
if(k&=h&&w2[k]==ww)
{ if(pp&=p2[k])
else if(pp&p2[next-1])
{ p2[next]=
w2[next]=next++;
while(k&=h&&p2[k]&=p2[next-1])k++;
while(k&=h)
{ p2[next]=p2[k];
w2[next]=w2[k];
next=next+1;
for(i=1;i&i++)
printf(&%2d%2d &,p2[i],w2[i]);
for(i=n;i&0;i--)
{ next=F[i];
pp=pk=p2[next];
ww=w2[next];
while(ww+w[i]&M&&next&F[i-1])
{ next=next-1;
pp=p2[next];
ww=w2[next];
if(ww+w[i]&=M&&next&F[i-1])px=pp+p[i];
if(px&pk&&ww+w[i]&=M)
{ s[i]=1; M=M-w[i];printf(&M=%d &,M);}
else s[i]=0;
for(i=1;i&=n;i++)
printf(&%2d &,s[i]); }
三亿文库包含各类专业文献、中学教育、生活休闲娱乐、文学作品欣赏、高等教育、外语学习资料、行业资料、专业论文、19解0-1背包问题的动态规划算法等内容。　
　实验内容分别编程实现动态规划算法和贪心法求 0-1 背包问题的最优解, 分析比较两 种算法的时间复杂度并验证分析结果。 二.实验目的 1、掌握动态规划算法和贪心法... 　1/2 相关文档推荐 第3章动态规划3-4节-0-1... 14页 免费
动态规划算法...解0-1背包问题的动态规划... 6页 1下载券
1 背包问题动态规划详解... 暂... 　算法:动态规划解决0-1背包问题_计算机软件及应用_IT/计算机_专业资料。算法:动态规划解决 0-1 背包问题 # include &stdafx.h& # include &stdio.h& int c[... 　解0-1背包问题的动态规划算法_计算机软件及应用_IT/计算机_专业资料。本文通过研究动态规划原理,提出了根据该原理解决0/1背包问题的方法与算法实现,并对算法的正确... 　动态规划解决算法0-1背包问题实验报告(含源代码)_计算机软件及应用_IT/计算机_...寻找一个满足约束条件,并使目标函数式达到最大的解向量,使得,而且 达到最大。... 　湖南涉外经济学院 实验报告 实验课程: 算法设计与分析 实验项目: 动态规划法解 0-1 背包问题 姓名 学院 实验地点 实验时间 指导老师 ... 　实验一 用动态规划解 0-1 背包问题 一、 1 2、使用动态规划法编程求解 0/...四、问题分析与算法设计 动态规划原理: 动态规划是一种将问题实例分解为更小的... 　班
上机时间: 一、实验目的与要求: 1、掌握动态规划算法求解问题的一般特征和步骤; 2、使用动态规划法编程,求解 0/1 背包问题。 二... 　0-1背包问题动态规划详解及代码_计算机软件及应用_IT/计算机_专业资料。0/1 背包问题动态规划详解及 C 代码动态规划是用空间换时间的一种方法的抽象。 其关键是...179115人阅读
01背包问题，是用来介绍动态规划算法最经典的例子，网上关于01背包问题的讲解也很多，我写这篇文章力争做到用最简单的方式，最少的公式把01背包问题讲解透彻。
01背包的状态转换方程&f[i,j] = Max{ f[i-1,j-Wi]+Pi( j &= Wi ), &f[i-1,j] }
f[i,j]表示在前i件物品中选择若干件放在承重为 j 的背包中，可以取得的最大价值。
Pi表示第i件物品的价值。
决策：为了背包中物品总价值最大化，第 i件物品应该放入背包中吗 ？
题目描述：
有编号分别为a,b,c,d,e的五件物品，它们的重量分别是2,2,6,5,4，它们的价值分别是6,3,5,4,6，现在给你个承重为10的背包，如何让背包里装入的物品具有最大的价值总和？
只要你能通过找规律手工填写出上面这张表就算理解了01背包的动态规划算法。
首先要明确这张表是至底向上，从左到右生成的。
为了叙述方便，用e2单元格表示e行2列的单元格，这个单元格的意义是用来表示只有物品e时，有个承重为2的背包，那么这个背包的最大价值是0，因为e物品的重量是4，背包装不了。
对于d2单元格，表示只有物品e，d时,承重为2的背包,所能装入的最大价值，仍然是0，因为物品e,d都不是这个背包能装的。
同理，c2=0，b2=3,a2=6。
对于承重为8的背包，a8=15,是怎么得出的呢？
根据01背包的状态转换方程，需要考察两个值，
一个是f[i-1,j],对于这个例子来说就是b8的值9，另一个是f[i-1,j-Wi]+Pi；
&f[i-1,j]表示我有一个承重为8的背包，当只有物品b,c,d,e四件可选时，这个背包能装入的最大价值
f[i-1,j-Wi]表示我有一个承重为6的背包（等于当前背包承重减去物品a的重量），当只有物品b,c,d,e四件可选时，这个背包能装入的最大价值
f[i-1,j-Wi]就是指单元格b6,值为9，Pi指的是a物品的价值，即6
由于f[i-1,j-Wi]+Pi = 9 + 6 = 15 大于f[i-1,j] = 9，所以物品a应该放入承重为8的背包
以下是actionscript3 的代码
public function get01PackageAnswer(bagItems:Array,bagSize:int):Array
var bagMatrix:Array=[];
var item:PackageI
for(i=0;i&bagItems.i++)
bagMatrix[i] = [0];
for(i=1;i&=bagSi++)
for(var j:int=0;j&bagItems.j++)
item = bagItems[j] as PackageI
if(item.weight & i)
//i背包转不下item
bagMatrix[j][i] = 0;
bagMatrix[j][i]=bagMatrix[j-1][i];
//将item装入背包后的价值总和
var itemInBag:
bagMatrix[j][i] = item.
itemInBag = bagMatrix[j-1][i-item.weight]+item.
bagMatrix[j][i] = (bagMatrix[j-1][i] & itemInBag ? bagMatrix[j-1][i] : itemInBag)
//find answer
var answers:Array=[];
var curSize:int = bagS
for(i=bagItems.length-1;i&=0;i--)
item = bagItems[i] as PackageI
if(curSize==0)
if(i==0 && curSize & 0)
answers.push(item.name);
if(bagMatrix[i][curSize]-bagMatrix[i-1][curSize-item.weight]==item.value)
answers.push(item.name);
curSize -= item.
PackageItem类
public class PackageItem
public var name:S
public var weight:
public var value:
public function PackageItem(name:String,weight:int,value:int)
this.name =
this.weight =
this.value =
var nameArr:Array=['a','b','c','d','e'];
var weightArr:Array=[2,2,6,5,4];
var valueArr:Array=[6,3,5,4,6];
var bagItems:Array=[];
for(var i:int=0;i&nameArr.i++)
var bagItem:PackageItem = new PackageItem(nameArr[i],weightArr[i],valueArr[i]);
bagItems[i]=bagI
var arr:Array = ac.get01PackageAnswer(bagItems,10);
&&相关文章推荐
* 以上用户言论只代表其个人观点，不代表CSDN网站的观点或立场
访问：448665次
积分：3533
积分：3533
排名：第9162名
原创：56篇
转载：15篇
评论：169条
(2)(1)(1)(6)(4)(4)(3)(1)(1)(4)(2)(2)(1)(1)(2)(5)(4)(1)(1)(1)(1)(1)(3)(7)(1)(1)(1)(1)(2)(5)(1)(1)