java0-1背包问题动态规划的简单介绍

0-1背包问题的多种解法代码（动态规划、贪心法、回溯法、分支限界法）

一.动态规划求解0-1背包问题

/************************************************************************/

/* 0-1背包问题：

/* 给定n种物品和一个背包

/* 物品i的重量为wi，其价值为vi

/* 背包的容量为c

/* 应如何选择装入背包的物品，使得装入背包中的物品

/* 的总价值最大？

/* 注：在选择装入背包的物品时，对物品i只有两种选择，

/* 即装入或不装入背包。不能将物品i装入多次，也

/* 不能只装入部分的物品i。

/*

/* 1. 0-1背包问题的形式化描述：

/* 给定c0, wi0, vi0, 0=i=n，要求找到一个n元的

/* 0-1向量(x1, x2, …, xn), 使得：

/* max sum_{i=1 to n} (vi*xi),且满足如下约束：

/* (1) sum_{i=1 to n} (wi*xi) = c

/* (2) xi∈{0, 1}, 1=i=n

/*

/* 2. 0-1背包问题的求解

/* 0-1背包问题具有最优子结构性质和子问题重叠性质，适于

/* 采用动态规划方法求解

/*

/* 2.1 最优子结构性质

/* 设(y1,y2,…,yn)是给定0-1背包问题的一个最优解，则必有

/* 结论，(y2,y3,…,yn)是如下子问题的一个最优解：

/* max sum_{i=2 to n} (vi*xi)

/* (1) sum_{i=2 to n} (wi*xi) = c – w1*y1

/* (2) xi∈{0, 1}, 2=i=n

/* 因为如若不然，则该子问题存在一个最优解(z2,z3,…,zn)，

/* 而(y2,y3,…,yn)不是其最优解。那么有：

/* sum_{i=2 to n} (vi*zi) sum_{i=2 to n} (vi*yi)

/* 且，w1*y1 + sum_{i=2 to n} (wi*zi) = c

/* 进一步有：

/* v1*y1 + sum_{i=2 to n} (vi*zi) sum_{i=1 to n} (vi*yi)

/* w1*y1 + sum_{i=2 to n} (wi*zi) = c

/* 这说明：(y1,z2,z3,…zn)是所给0-1背包问题的更优解，那么

/* 说明(y1,y2,…,yn)不是问题的最优解，与前提矛盾，所以最优

/* 子结构性质成立。

/*

/* 2.2 子问题重叠性质

/* 设所给0-1背包问题的子问题 P(i,j)为：

/* max sum_{k=i to n} (vk*xk)

/* (1) sum_{k=i to n} (wk*xk) = j

/* (2) xk∈{0, 1}, i=k=n

/* 问题P(i,j)是背包容量为j、可选物品为i,i+1,…,n时的子问题

/* 设m(i,j)是子问题P(i,j)的最优值，即最大总价值。则根据最优

/* 子结构性质，可以建立m(i,j)的递归式：

/* a. 递归初始 m(n,j)

/* //背包容量为j、可选物品只有n，若背包容量j大于物品n的

/* //重量，则直接装入；否则无法装入。

/* m(n,j) = vn, j=wn

/* m(n,j) = 0, 0=jwn

/* b. 递归式 m(i,j)

/* //背包容量为j、可选物品为i,i+1,…,n

/* //如果背包容量jwi，则根本装不进物品i，所以有：

/* m(i,j) = m(i+1,j), 0=jwi

/* //如果j=wi，则在不装物品i和装入物品i之间做出选择

/* 不装物品i的最优值：m(i+1,j)

/* 装入物品i的最优值：m(i+1, j-wi) + vi

/* 所以：

/* m(i,j) = max {m(i+1,j), m(i+1, j-wi) + vi}, j=wi

/*

/************************************************************************/

#define max(a,b) (((a) (b)) ? (a) : (b))

#define min(a,b) (((a) (b)) ? (a) : (b))

template typename Type

void Knapsack(Type* v, int *w, int c, int n, Type **m)

{

//递归初始条件

int jMax = min(w[n] – 1, c);

for (int j=0; j=jMax; j++) {

m[n][j] = 0;

}

for (j=w[n]; j=c; j++) {

m[n][j] = v[n];

}

//i从2到n-1，分别对j=wi和0=jwi即使m(i,j)

for (int i=n-1; i1; i–) {

jMax = min(w[i] – 1, c);

for (int j=0; j=jMax; j++) {

m[i][j] = m[i+1][j];

}

for (j=w[i]; j=c; j++) {

m[i][j] = max(m[i+1][j], m[i+1][j-w[i]]+v[i]);

}

}

m[1][c] = m[2][c];

if (c = w[1]) {

m[1][c] = max(m[1][c], m[2][c-w[1]]+v[1]);

}

}

template typename Type

void TraceBack(Type **m, int *w, int c, int n, int* x)

{

for (int i=1; in; i++) {

if(m[i][c] == m[i+1][c]) x[i] = 0;

else {

x[i] = 1;

c -= w[i];

}

}

x[n] = (m[n][c])? 1:0;

}

int main(int argc, char* argv[])

{

int n = 5;

int w[6] = {-1, 2, 2, 6, 5, 4};

int v[6] = {-1, 6, 3, 5, 4, 6};

int c = 10;

int **ppm = new int*[n+1];

for (int i=0; in+1; i++) {

ppm[i] = new int[c+1];

}

int x[6];

Knapsackint(v, w, c, n, ppm);

TraceBackint(ppm, w, c, n, x);

return 0;

}

二.贪心算法求解0-1背包问题

1.贪心法的基本思路：

——从问题的某一个初始解出发逐步逼近给定的目标，以尽可能快的地求得更好的解。当达到某算法中的某一步不能再继续前进时，算法停止。

该算法存在问题：

1).不能保证求得的最后解是最佳的；

2).不能用来求最大或最小解问题；

3).只能求满足某些约束条件的可行解的范围。

实现该算法的过程：

从问题的某一初始解出发；

while 能朝给定总目标前进一步 do

求出可行解的一个解元素；

由所有解元素组合成问题的一个可行解；

2.例题分析

1).[背包问题]有一个背包，背包容量是M=150。有7个物品，物品可以分割成任意大小。

要求尽可能让装入背包中的物品总价值最大，但不能超过总容量。

物品 A B C D E F G

重量 35 30 60 50 40 10 25

价值 10 40 30 50 35 40 30

分析：

目标函数： ∑pi最大

约束条件是装入的物品总重量不超过背包容量：∑wi=M( M=150)

（1）根据贪心的策略，每次挑选价值最大的物品装入背包，得到的结果是否最优？

（2）每次挑选所占空间最小的物品装入是否能得到最优解？

（3）每次选取单位容量价值最大的物品，成为解本题的策略。

程序代码:(环境:c++)

#includeiostream.h

#define max 100 //最多物品数

void sort (int n,float a[max],float b[max]) //按价值密度排序

{

int j,h,k;

float t1,t2,t3,c[max];

for(k=1;k=n;k++)

c[k]=a[k]/b[k];

for(h=1;hn;h++)

for(j=1;j=n-h;j++)

if(c[j]c[j+1])

{t1=a[j];a[j]=a[j+1];a[j+1]=t1;

t2=b[j];b[j]=b[j+1];b[j+1]=t2;

t3=c[j];c[j]=c[j+1];c[j+1]=t3;

}

}

void knapsack(int n,float limitw,float v[max],float w[max],int x[max])

{float c1; //c1为背包剩余可装载重量

int i;

sort(n,v,w); //物品按价值密度排序

c1=limitw;

for(i=1;i=n;i++)

{

if(w[i]c1)break;

x[i]=1; //x[i]为1时，物品i在解中

c1=c1-w[i];

}

}

void main()

{int n,i,x[max];

float v[max],w[max],totalv=0,totalw=0,limitw;

cout”请输入n和limitw:”;

cinn limitw;

for(i=1;i=n;i++)

x[i]=0; //物品选择情况表初始化为0

cout”请依次输入物品的价值：”endl;

for(i=1;i=n;i++)

cinv[i];

coutendl;

cout”请依次输入物品的重量：”endl;

for(i=1;i=n;i++)

cinw[i];

coutendl;

knapsack (n,limitw,v,w,x);

cout”the selection is:”;

for(i=1;i=n;i++)

{

coutx[i];

if(x[i]==1)

totalw=totalw+w[i];

}

coutendl;

cout”背包的总重量为：”totalwendl; //背包所装载总重量

cout”背包的总价值为：”totalvendl; //背包的总价值

}

三.回溯算法求解0-1背包问题

1.0-l背包问题是子集选取问题。

一般情况下，0-1背包问题是NP难题。0-1背包

问题的解空间可用子集树表示。解0-1背包问题的回溯法与装载问题的回溯法十分类

似。在搜索解空间树时，只要其左儿子结点是一个可行结点，搜索就进入其左子树。当

右子树有可能包含最优解时才进入右子树搜索。否则将右子树剪去。设r是当前剩余

物品价值总和；cp是当前价值；bestp是当前最优价值。当cp+r≤bestp时，可剪去右

子树。计算右子树中解的上界的更好方法是将剩余物品依其单位重量价值排序，然后

依次装入物品，直至装不下时，再装入该物品的一部分而装满背包。由此得到的价值是

右子树中解的上界。

2.解决办法思路：

为了便于计算上界，可先将物品依其单位重量价值从大到小排序，此后只要顺序考

察各物品即可。在实现时，由bound计算当前结点处的上界。在搜索解空间树时，只要其左儿子节点是一个可行结点，搜索就进入左子树，在右子树中有可能包含最优解是才进入右子树搜索。否则将右子树剪去。

回溯法是一个既带有系统性又带有跳跃性的的搜索算法。它在包含问题的所有解的解空间树中，按照深度优先的策略，从根结点出发搜索解空间树。算法搜索至解空间树的任一结点时，总是先判断该结点是否肯定不包含问题的解。如果肯定不包含，则跳过对以该结点为根的子树的系统搜索，逐层向其祖先结点回溯。否则，进入该子树，继续按深度优先的策略进行搜索。回溯法在用来求问题的所有解时，要回溯到根，且根结点的所有子树都已被搜索遍才结束。而回溯法在用来求问题的任一解时，只要搜索到问题的一个解就可以结束。这种以深度优先的方式系统地搜索问题的解的算法称为回溯法，它适用于解一些组合数较大的问题。

2.算法框架：

a.问题的解空间：应用回溯法解问题时，首先应明确定义问题的解空间。问题的解空间应到少包含问题的一个（最优）解。

b.回溯法的基本思想：确定了解空间的组织结构后，回溯法就从开始结点（根结点）出发，以深度优先的方式搜索整个解空间。这个开始结点就成为一个活结点，同时也成为当前的扩展结点。在当前的扩展结点处，搜索向纵深方向移至一个新结点。这个新结点就成为一个新的活结点，并成为当前扩展结点。如果在当前的扩展结点处不能再向纵深方向移动，则当前扩展结点就成为死结点。换句话说，这个结点不再是一个活结点。此时，应往回移动（回溯）至最近的一个活结点处，并使这个活结点成为当前的扩展结点。回溯法即以这种工作方式递归地在解空间中搜索，直至找到所要求的解或解空间中已没有活结点时为止。

3.运用回溯法解题通常包含以下三个步骤：

a.针对所给问题，定义问题的解空间；

b.确定易于搜索的解空间结构；

c.以深度优先的方式搜索解空间，并且在搜索过程中用剪枝函数避免无效搜索；

#includeiostream

using namespace std;

class Knap

{

friend int Knapsack(int p[],int w[],int c,int n );

public:

void print()

{

for(int m=1;m=n;m++)

{

coutbestx[m]” “;

}

coutendl;

};

private:

int Bound(int i);

void Backtrack(int i);

int c;//背包容量

int n; //物品数

int *w;//物品重量数组

int *p;//物品价值数组

int cw;//当前重量

int cp;//当前价值

int bestp;//当前最优值

int *bestx;//当前最优解

int *x;//当前解

};

int Knap::Bound(int i)

{

//计算上界

int cleft=c-cw;//剩余容量

int b=cp;

//以物品单位重量价值递减序装入物品

while(i=nw[i]=cleft)

{

cleft-=w[i];

b+=p[i];

i++;

}

//装满背包

if(i=n)

b+=p[i]/w[i]*cleft;

return b;

}

void Knap::Backtrack(int i)

{

if(in)

{

if(bestpcp)

{

for(int j=1;j=n;j++)

bestx[j]=x[j];

bestp=cp;

}

return;

}

if(cw+w[i]=c) //搜索左子树

{

x[i]=1;

cw+=w[i];

cp+=p[i];

Backtrack(i+1);

cw-=w[i];

cp-=p[i];

}

if(Bound(i+1)bestp)//搜索右子树

{

x[i]=0;

Backtrack(i+1);

}

}

class Object

{

friend int Knapsack(int p[],int w[],int c,int n);

public:

int operator=(Object a)const

{

return (d=a.d);

}

private:

int ID;

float d;

};

int Knapsack(int p[],int w[],int c,int n)

{

//为Knap::Backtrack初始化

int W=0;

int P=0;

int i=1;

Object *Q=new Object[n];

for(i=1;i=n;i++)

{

Q[i-1].ID=i;

Q[i-1].d=1.0*p[i]/w[i];

P+=p[i];

W+=w[i];

}

if(W=c)

return P;//装入所有物品

//依物品单位重量排序

float f;

for( i=0;in;i++)

for(int j=i;jn;j++)

{

if(Q[i].dQ[j].d)

{

f=Q[i].d;

Q[i].d=Q[j].d;

Q[j].d=f;

}

}

Knap K;

K.p = new int[n+1];

K.w = new int[n+1];

K.x = new int[n+1];

K.bestx = new int[n+1];

K.x[0]=0;

K.bestx[0]=0;

for( i=1;i=n;i++)

{

K.p[i]=p[Q[i-1].ID];

K.w[i]=w[Q[i-1].ID];

}

K.cp=0;

K.cw=0;

K.c=c;

K.n=n;

K.bestp=0;

//回溯搜索

K.Backtrack(1);

K.print();

delete [] Q;

delete [] K.w;

delete [] K.p;

return K.bestp;

}

void main()

{

int *p;

int *w;

int c=0;

int n=0;

int i=0;

char k;

cout”0-1背包问题——回溯法 “endl;

cout” by zbqplayer “endl;

while(k)

{

cout”请输入背包容量(c)：”endl;

cinc;

cout”请输入物品的个数(n)：”endl;

cinn;

p=new int[n+1];

w=new int[n+1];

p[0]=0;

w[0]=0;

cout”请输入物品的价值(p)：”endl;

for(i=1;i=n;i++)

cinp[i];

cout”请输入物品的重量(w)：”endl;

for(i=1;i=n;i++)

cinw[i];

cout”最优解为(bestx)：”endl;

cout”最优值为(bestp)：”endl;

coutKnapsack(p,w,c,n)endl;

cout”[s] 重新开始”endl;

cout”[q] 退出”endl;

cink;

}

四.分支限界法求解0-1背包问题

1.问题描述：已知有N个物品和一个可以容纳M重量的背包，每种物品I的重量为WEIGHT，一个只能全放入或者不放入，求解如何放入物品，可以使背包里的物品的总效益最大。

2.设计思想与分析：对物品的选取与否构成一棵解树，左子树表示不装入，右表示装入，通过检索问题的解树得出最优解，并用结点上界杀死不符合要求的结点。

#include iostream.h

struct good

{

int weight;

int benefit;

int flag;//是否可以装入标记

};

int number=0;//物品数量

int upbound=0;

int curp=0, curw=0;//当前效益值与重量

int maxweight=0;

good *bag=NULL;

void Init_good()

{

bag=new good [number];

for(int i=0; inumber; i++)

{

cout”请输入第件”i+1″物品的重量:”;

cinbag[i].weight;

cout”请输入第件”i+1″物品的效益:”;

cinbag[i].benefit;

bag[i].flag=0;//初始标志为不装入背包

coutendl;

}

}

int getbound(int num, int *bound_u)//返回本结点的c限界和u限界

{

for(int w=curw, p=curp; numnumber (w+bag[num].weight)=maxweight; num++)

{

w=w+bag[num].weight;

p=w+bag[num].benefit;

}

*bound_u=p+bag[num].benefit;

return ( p+bag[num].benefit*((maxweight-w)/bag[num].weight) );

}

void LCbag()

{

int bound_u=0, bound_c=0;//当前结点的c限界和u限界

for(int i=0; inumber; i++)//逐层遍历解树决定是否装入各个物品

{

if( ( bound_c=getbound(i+1, bound_u) )upbound )//遍历左子树

upbound=bound_u;//更改已有u限界,不更改标志

if( getbound(i, bound_u)bound_c )//遍历右子树

//若装入，判断右子树的c限界是否大于左子树根的c限界，是则装入

{

upbound=bound_u;//更改已有u限界

curp=curp+bag[i].benefit;

curw=curw+bag[i].weight;//从已有重量和效益加上新物品

bag[i].flag=1;//标记为装入

}

}

}

void Display()

{

cout”可以放入背包的物品的编号为：”;

for(int i=0; inumber; i++)

if(bag[i].flag0)

couti+1″ “;

coutendl;

delete []bag;

}

动态规划中的0-1背包问题怎么去理解？要求给出具体实例和详细步骤。。。

* 一个旅行者有一个最多能用M公斤的背包，现在有N件物品，

它们的重量分别是W1，W2，…,Wn,

它们的价值分别为P1,P2,…,Pn.

若每种物品只有一件求旅行者能获得最大总价值。

输入格式：

M,N

W1,P1

W2,P2

……

输出格式：

X

*/

因为背包最大容量M未知。所以，我们的程序要从1到M一个一个的试。比如，开始任选N件物品的一个。看对应M的背包，能不能放进去，如果能放进去，并且还有多的空间，则，多出来的空间里能放N-1物品中的最大价值。怎么能保证总选择是最大价值呢？看下表。

测试数据：

10,3

3,4

4,5

5,6

c[i][j]数组保存了1,2,3号物品依次选择后的最大价值.

这个最大价值是怎么得来的呢?从背包容量为0开始,1号物品先试,0,1,2,的容量都不能放.所以置0,背包容量为3则里面放4.这样,这一排背包容量为4,5,6,….10的时候，最佳方案都是放4.假如1号物品放入背包.则再看2号物品.当背包容量为3的时候，最佳方案还是上一排的最价方案c为4.而背包容量为5的时候，则最佳方案为自己的重量5.背包容量为7的时候，很显然是5加上一个值了。加谁??很显然是7-4=3的时候.上一排 c3的最佳方案是4.所以。总的最佳方案是5+4为9.这样.一排一排推下去。最右下放的数据就是最大的价值了。(注意第3排的背包容量为7的时候,最佳方案不是本身的6.而是上一排的9.说明这时候3号物品没有被选.选的是1,2号物品.所以得9.)

从以上最大价值的构造过程中可以看出。

f(n,m)=max{f(n-1,m), f(n-1,m-w[n])+P(n,m)}这就是书本上写的动态规划方程.这回清楚了吗?

下面是实际程序:

#includestdio.h

int c[10][100];/*对应每种情况的最大价值*/

int knapsack(int m,int n)

{

int i,j,w[10],p[10];

for(i=1;in+1;i++)

scanf(“\n%d,%d”,w[i],p[i]);

for(i=0;i10;i++)

for(j=0;j100;j++)

c[i][j]=0;/*初始化数组*/

for(i=1;in+1;i++)

for(j=1;jm+1;j++)

{

if(w[i]=j) /*如果当前物品的容量小于背包容量*/

{

if(p[i]+c[i-1][j-w[i]]c[i-1][j])

/*如果本物品的价值加上背包剩下的空间能放的物品的价值*/

/*大于上一次选择的最佳方案则更新c[i][j]*/

c[i][j]=p[i]+c[i-1][j-w[i]];

else

c[i][j]=c[i-1][j];

}

else c[i][j]=c[i-1][j];

}

return(c[n][m]);

}

int main()

{

int m,n;int i,j;

scanf(“%d,%d”,m,n);

printf(“Input each one:\n”);

printf(“%d”,knapsack(m,n));

printf(“\n”);/*下面是测试这个数组,可删除*/

for(i=0;i10;i++)

for(j=0;j15;j++)

{

printf(“%d “,c[i][j]);

if(j==14)printf(“\n”);

}

system(“pause”);

}

用动态规划算法怎样求解01背包问题

动态规划主要解决的是多阶段的决策问题。

01背包中，状态为背包剩余的容量，阶段是每一个物品，决策是是否选择当前的物品。

所以用动态规划来解决是非常贴切的。

我们设f[V]表示已经使用容量为V时所能获得的最大价值，w[i]表示i物品的质量，c[i]表示i物品的价值。

for(int i=1;i=n;i++)

    for(int j=V;j=w[i];j–)

        f[j]=max(f[j],f[j-w[i]]+c[i]);

这便是所谓的一个状态转移方程。

f[j]表示在已经使用容量为j时的最大价值，f[j-w[i]]表示在已经使用容量为j-w[i]时的最大价值。

f[j]可以由f[j-w[i]]这个状态转移到达，表示选取w[i]这个物品，并从而获得价值为c[i]。

而每次f[j]会在选与不选中决策选出最优的方案。

从每一个物品，也就是每一个阶段的局部最优推出最后的全局最优值。这样就解决了01背包问题

求动态规划0-1背包算法解释

01背包问题

题目

有N件物品和一个容量为V的背包。第i件物品的费用是c[i]，价值是w[i]。求解将哪些物品装入背包可使价值总和最大。

基本思路

这是最基础的背包问题，特点是：每种物品仅有一件，可以选择放或不放。

用子问题定义状态：即f[i][v]表示前i件物品恰放入一个容量为v的背包可以获得的最大价值。则其状态转移方程便是：

f[i][v]=max{f[i-1][v],f[i-1][v-c[i]]+w[i]}

这个方程非常重要，基本上所有跟背包相关的问题的方程都是由它衍生出来的。所以有必要将它详细解释一下：“将前i件物品放入容量为v的背包中”这个子问题，若只考虑第i件物品的策略（放或不放），那么就可以转化为一个只牵扯前i-1件物品的问题。如果不放第i件物品，那么问题就转化为“前i-1件物 品放入容量为v的背包中”，价值为f[i-1][v]；如果放第i件物品，那么问题就转化为“前i-1件物品放入剩下的容量为v-c[i]的背包中”，此时能获得的最大价值就是f[i-1][v-c[i]]再加上通过放入第i件物品获得的价值w[i]。

优化空间复杂度

以上方法的时间和空间复杂度均为O(VN)，其中时间复杂度应该已经不能再优化了，但空间复杂度却可以优化到O。

先考虑上面讲的基本思路如何实现，肯定是有一个主循环i=1..N，每次算出来二维数组f[i][0..V]的所有值。那么，如果只用一个数组 f[0..V]，能不能保证第i次循环结束后f[v]中表示的就是我们定义的状态f[i][v]呢？f[i][v]是由f[i-1][v]和f[i-1] [v-c[i]]两个子问题递推而来，能否保证在推f[i][v]时（也即在第i次主循环中推f[v]时）能够得到f[i-1][v]和f[i-1] [v-c[i]]的值呢？事实上，这要求在每次主循环中我们以v=V..0的顺序推f[v]，这样才能保证推f[v]时f[v-c[i]]保存的是状态 f[i-1][v-c[i]]的值。伪代码如下：

for i=1..N

for v=V..0

f[v]=max{f[v],f[v-c[i]]+w[i]};

其中的f[v]=max{f[v],f[v-c[i]]}一句恰就相当于我们的转移方程f[i][v]=max{f[i-1][v],f[i-1][v-c[i]]}，因为现在的f[v-c[i]]就相当于原来的f[i-1][v-c[i]]。如果将v的循环顺序从上面的逆序改成顺序的话，那么则成了f[i][v]由f[i][v-c[i]]推知，与本题意不符，但它却是另一个重要的背包问题P02最简捷的解决方案，故学习只用一维数组解01背包问题是十分必要的。

事实上，使用一维数组解01背包的程序在后面会被多次用到，所以这里抽象出一个处理一件01背包中的物品过程，以后的代码中直接调用不加说明。

过程ZeroOnePack，表示处理一件01背包中的物品，两个参数cost、weight分别表明这件物品的费用和价值。

procedure ZeroOnePack(cost,weight)

for v=V..cost

f[v]=max{f[v],f[v-cost]+weight}

注意这个过程里的处理与前面给出的伪代码有所不同。前面的示例程序写成v=V..0是为了在程序中体现每个状态都按照方程求解了，避免不必要的思维复杂度。而这里既然已经抽象成看作黑箱的过程了，就可以加入优化。费用为cost的物品不会影响状态f[0..cost-1]，这是显然的。

有了这个过程以后，01背包问题的伪代码就可以这样写：

for i=1..N

ZeroOnePack(c[i],w[i]);

初始化的细节问题

我们看到的求最优解的背包问题题目中，事实上有两种不太相同的问法。有的题目要求“恰好装满背包”时的最优解，有的题目则并没有要求必须把背包装满。一种区别这两种问法的实现方法是在初始化的时候有所不同。

如果是第一种问法，要求恰好装满背包，那么在初始化时除了f[0]为0其它f[1..V]均设为-∞，这样就可以保证最终得到的f[N]是一种恰好装满背包的最优解。

如果并没有要求必须把背包装满，而是只希望价格尽量大，初始化时应该将f[0..V]全部设为0。

为什么呢？可以这样理解：初始化的f数组事实上就是在没有任何物品可以放入背包时的合法状态。如果要求背包恰好装满，那么此时只有容量为0的背包可能被价值为0的nothing“恰好装满”，其它容量的背包均没有合法的解，属于未定义的状态，它们的值就都应该是-∞了。如果背包并非必须被装满，那么 任何容量的背包都有一个合法解“什么都不装”，这个解的价值为0，所以初始时状态的值也就全部为0了。

这个小技巧完全可以推广到其它类型的背包问题，后面也就不再对进行状态转移之前的初始化进行讲解。

一个常数优化

前面的伪代码中有 for v=V..1，可以将这个循环的下限进行改进。

由于只需要最后f[v]的值，倒推前一个物品，其实只要知道f[v-w[n]]即可。以此类推，对以第j个背包，其实只需要知道到f[v-sum{w[j..n]}]即可，即代码中的

for i=1..N

for v=V..0

可以改成

for i=1..n

bound=max{V-sum{w[i..n]},c[i]}

for v=V..bound

这对于V比较大时是有用的。

小结

01背包问题是最基本的背包问题，它包含了背包问题中设计状态、方程的最基本思想，另外，别的类型的背包问题往往也可以转换成01背包问题求解。故一定要仔细体会上面基本思路的得出方法，状态转移方程的意义，以及最后怎样优化的空间复杂度。