下载文档原格式
背包问题01背包问题题⽬有N件物品和⼀个容量为M的背包，每种物品只可以取⼀件。
第i件物品的费⽤是c[i]，价值是v[i]。
求解将哪些物品装⼊背包可使价值总和最⼤。
分析这是最基础的背包问题，特点是：每种物品仅有⼀件，可以选择放或不放。
⽤⼦问题定义状态：即f[i][j]表⽰前i件物品恰放⼊⼀个容量为j的背包可以获得的最⼤价值。
则其状态转移⽅程便是：f[i][j]=max{f[i-1][j],f[i-1][j-c[i]]+v[i]}优化空间复杂度即改⽤⼀维数组f[j]存储第i个物品时剩余空间为j时的背包的最⼤价值。
注意到j-c[i]<j这个关系，当j=0……M顺序推f[j]，则后⾯的到的f[j]将会使⽤到当前i状态下新⽣成的f[j-c[i]]，⽽不是我们所需的i-1状态时的f[j-c[i]]。
因此，在每次主循环中我们以j=M……0顺序推f[j]，这样才能保证推f[j]时f[j-c[i]]保存的是状态f[i-1][j-c[i]]的值。
参考代码完全背包问题题⽬有N件物品和⼀个容量为M的背包，每种物品都有⽆限件可⽤。
第i件物品的费⽤是c[i]，价值是v[i]。
求解将哪些物品装⼊背包可使价值总和最⼤。
分析类似01背包问题，但与它相关的策略已并⾮取或不取两种，⽽是有取0件、取1件、取2件……。
如果仍然按照解01背包时的思路，令f[i][j]表⽰前i种物品恰放⼊⼀个容量为j的背包的最⼤权值。
仍然可以按照每种物品不同的策略写出状态转移⽅程：f[i][j]=max{ f[i-1][j-k*c[i]]+k*v[i] | 0<=k*c[i]<=M }优化时间复杂度若两件物品i、j满⾜c[i]<=c[j]且w[i]>=w[j]，则将物品j去掉，不⽤考虑。
将费⽤⼤于M的物品去掉，然后使⽤类似计数排序的做法，计算出费⽤相同的物品中价值最⾼的是哪个。
转化为01背包问题求解最简单的想法是：考虑到第i种物品最多选M/c[i]件，于是可以把第i种物品转化为M/c[i]件费⽤及价值均不变的物品，然后求解这个01背包问题。
贪⼼算法-01背包问题1、问题描述：给定n种物品和⼀背包。
物品i的重量是wi，其价值为vi，背包的容量为C。
问:应如何选择装⼊背包的物品，使得装⼊背包中物品的总价值最⼤?形式化描述：给定c >0, wi >0, vi >0 , 1≤i≤n.要求找⼀n元向量(x1,x2,…,xn,), xi∈{0,1}, ∋ ∑ wi xi≤c,且∑ vi xi达最⼤.即⼀个特殊的整数规划问题。
2、最优性原理：设(y1,y2,…,yn)是 (3.4.1)的⼀个最优解.则(y2,…,yn)是下⾯相应⼦问题的⼀个最优解:证明:使⽤反证法。
若不然,设(z2,z3,…,zn)是上述⼦问题的⼀个最优解,⽽(y2,y3,…,yn)不是它的最优解。
显然有∑vizi > ∑viyi (i=2,…,n)且 w1y1+ ∑wizi<= c因此 v1y1+ ∑vizi (i=2,…,n) > ∑ viyi, (i=1,…,n)说明(y1,z2, z3,…,zn)是(3.4.1)0-1背包问题的⼀个更优解,导出(y1,y2,…,yn)不是背包问题的最优解,⽭盾。
3、递推关系：设所给0-1背包问题的⼦问题的最优值为m(i，j)，即m(i，j)是背包容量为j，可选择物品为i，i+1，…，n时0-1背包问题的最优值。
由0-1背包问题的最优⼦结构性质，可以建⽴计算m(i，j)的递归式:注:(3.4.3)式此时背包容量为j，可选择物品为i。
此时在对xi作出决策之后,问题处于两种状态之⼀:(1)背包剩余容量是j,没产⽣任何效益；(2)剩余容量j-wi,效益值增长了vi ；使⽤递归C++代码如下：#include<iostream>using namespace std;const int N=3;const int W=50;int weights[N+1]={0,10,20,30};int values[N+1]={0,60,100,120};int V[N+1][W+1]={0};int knapsack(int i,int j){int value;if(V[i][j]<0){if(j<weights[i]){value=knapsack(i-1,j);}else{value=max(knapsack(i-1,j),values[i]+knapsack(i-1,j-weights[i]));}V[i][j]=value;}return V[i][j];}int main(){int i,j;for(i=1;i<=N;i++)for(j=1;j<=W;j++)V[i][j]=-1;cout<<knapsack(3,50)<<endl;cout<<endl;}不使⽤递归的C++代码：简单⼀点的修改//3d10-1 动态规划背包问题#include <iostream>using namespace std;const int N = 4;void Knapsack(int v[],int w[],int c,int n,int m[][10]);void Traceback(int m[][10],int w[],int c,int n,int x[]);int main(){int c=8;int v[]={0,2,1,4,3},w[]={0,1,4,2,3};//下标从1开始int x[N+1];int m[10][10];cout<<"待装物品重量分别为："<<endl;for(int i=1; i<=N; i++){cout<<w[i]<<" ";}cout<<endl;cout<<"待装物品价值分别为："<<endl;for(int i=1; i<=N; i++){cout<<v[i]<<" ";}cout<<endl;Knapsack(v,w,c,N,m);cout<<"背包能装的最⼤价值为："<<m[1][c]<<endl;Traceback(m,w,c,N,x);cout<<"背包装下的物品编号为："<<endl;for(int i=1; i<=N; i++){if(x[i]==1){cout<<i<<" ";}}cout<<endl;return 0;}void Knapsack(int v[],int w[],int c,int n,int m[][10]){int jMax = min(w[n]-1,c);//背包剩余容量上限范围[0~w[n]-1] for(int j=0; j<=jMax;j++){m[n][j]=0;}for(int j=w[n]; j<=c; j++)//限制范围[w[n]~c]{m[n][j] = v[n];}for(int i=n-1; i>1; i--){jMax = min(w[i]-1,c);for(int j=0; j<=jMax; j++)//背包不同剩余容量j<=jMax<c{m[i][j] = m[i+1][j];//没产⽣任何效益}for(int j=w[i]; j<=c; j++) //背包不同剩余容量j-wi >c{m[i][j] = max(m[i+1][j],m[i+1][j-w[i]]+v[i]);//效益值增长vi }}m[1][c] = m[2][c];if(c>=w[1]){m[1][c] = max(m[1][c],m[2][c-w[1]]+v[1]);}}//x[]数组存储对应物品0-1向量,0不装⼊背包，1表⽰装⼊背包void Traceback(int m[][10],int w[],int c,int n,int x[]){for(int i=1; i<n; 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;}运⾏结果：算法执⾏过程对m[][]填表及Traceback回溯过程如图所⽰：从m(i，j)的递归式容易看出，算法Knapsack需要O(nc)计算时间; Traceback需O(n)计算时间；算法总体需要O(nc)计算时间。
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的背包，如何让背包里装入的物品具有最首先要明确这张表是从右到左,至底向上生成的。
为了叙述方便，用e10单元格表示e行10列的单元格，这个单元格的意义是用来表示只有物品e时，有个承重为10的背包，那么这个背包的最大价值是6，因为e物品的重量是4，背包装的了，把e装进去后价值为6。
然后是e9单元格表示背包承重9，只有物品e, e装进去后，背包价值为6，接着是e8, e7单元格，一直到e3单元格表示背包承重3，但物品e承重4，装不了，所以e3=0,对于d10单元格，表示只有物品e，d时,承重为10的背包,所能装入的最大价值，是10，因为物品e,d这个背包都能装进去。
对于承重为9的背包，d9=10,是怎么得出的呢？根据01背包的状态转换方程，需要考察两个值，一个是f[i-1,j],对于这个例子来说就是e9的值6，另一个是f[i-1,j-Wi]+Pi；在这里，f[i-1,j]表示我有一个承重为9的背包，当只有物品e可选时，这个背包能装入的最大价值f[i-1,j-Wi]表示我有一个承重为4的背包（等于当前背包承重减去物品d的重量），当只有物品e可选时，这个背包能装入的最大价值f[i-1,j-Wi]就是指单元格e4值为6，Pi指的是d物品的价值，即4由于f[i-1,j-Wi]+Pi = 6 + 4 = 10 大于f[i-1,j] = 6，所以物品d应该放入承重为9的背包，所以d9=10.。
一、01背包问题1、题目：有N件物品和一个容量为V的背包。
第i件物品的费用是c[i]，价值是w[i]。
求解将哪些物品装入背包可使价值总和最大。
2、基本思路：这是最基础的背包问题，特点是：每种物品仅有一件，可以选择放或不放。
用子问题定义状态：即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]。
3、优化空间复杂度：以上方法的时间和空间复杂度均为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]]的值。
二维背包问题经典例题
二维背包问题是一个经典的动态规划问题，下面是一个具体的例题：
题目描述：
有N件物品和一个容量是V的背包，背包能承受的最大重量是M。
每件物品只能用一次。
体积是vi，重量是mi，价值是wi。
求解将哪些物品装入背包，可使物品总体积不超过背包容量，总重量不超过背包可承受的最大重量，且价值总和最大。
输出最大价值。
输入格式：
第一行两个整数，N，V，M，用空格隔开，分别表示物品件数、背包容积和背包可承受的最大重量。
接下来有N行，每行三个整数vi，mi，wi，用空格隔开，分别表示第i件物品的体积、重量和价值。
输出格式：
输出一个整数，表示最大价值。
输入样例：
4 5 6
1 2 32
4 4 43
4 5 54
5 6 6
输出样例：8
思路分析：
二维背包问题可以通过建立一个三维数组f[i][j][k]来解决，其中f[i][j][k]表示在前i个物品中选出体积不超过j、质量不超过k的物品的最大价值。
状态转移方程为f[i][j][k]=max(f[i-1][j][k], f[i-1][j-v][k-m]+w)，其中v表示第i个物品的体
积，m表示第i个物品的质量，w表示第i个物品的价值。
由于数组是三维的，因此可以使用滚动数组来优化空间复杂度。
具体实现时，可以将j和k的枚举顺序改为从大到小，以防止需要用到的状态被覆盖。
背包问题的数学模型摘要：1.背包问题的定义2.背包问题的数学模型3.背包问题的求解方法4.背包问题的应用实例正文：一、背包问题的定义背包问题是一个经典的优化问题，它的问题是给定一个背包和n 种物品，其中，背包的容量为V，第i 种物品的质量为c_i，价值为p_i，如何通过物品选择，使得装入背包中的物品总价值最大。
二、背包问题的数学模型为了更好地理解背包问题，我们可以将其建立一个数学模型。
假设有n 种物品，分别用v_i 表示第i 种物品的价值，c_i 表示第i 种物品的质量，那么背包问题的数学模型可以表示为：f(x) = max {v_1x_1 + v_2x_2 +...+ v_nx_n}s.t.c_1x_1 + c_2x_2 +...+ c_nx_n <= Vx_i >= 0, i = 1,2,...,n其中，f(x) 表示背包中物品的总价值，x_i 表示第i 种物品的数量，V 表示背包的容量，c_i 表示第i 种物品的质量，v_i 表示第i 种物品的价值。
三、背包问题的求解方法背包问题的求解方法有很多，常见的有动态规划法、回溯法、贪心算法等。
这里我们以动态规划法为例进行介绍。
动态规划法的基本思想是将问题分解为子问题，通过求解子问题，最终得到原问题的解。
对于背包问题，我们可以将问题分解为：在容量为V 的情况下，如何选择物品使得总价值最大。
然后，我们可以通过递归的方式，依次求解子问题，最终得到原问题的解。
四、背包问题的应用实例背包问题是一个非常实用的优化问题，它在现实生活中有很多应用。
例如，一个果农需要根据市场需求和成本，选择合适的水果进行装箱；一个旅行者需要根据行李箱的容量和物品的价值，选择携带的物品等。
这些都可以通过背包问题来求解。
综上所述，背包问题是一个经典的优化问题，它有着广泛的应用。
背包问题之零⼀背包注:参考⽂献《背包九讲》.零⼀背包问题⼀:题⽬描述 有 N 件物品和⼀个容量为 V 的背包.放⼊第 i 件物品耗⽤的费⽤为C i(即所占⽤背包的体积),得到的价值是 W i.求将哪些物品装⼊背包所得到的总价值最⼤.⼆:基本思路 01背包是最基础的背包问题,这道题的特点是每种物品仅有⼀件,可以选择放或不放,且不要求背包必须被放满,只要求最后的总价值最⼤. ⽤⼦问题定义状态:F[i][v] 表⽰对于前 i 件物品,当背包容量为 v 时所能得到的价值最⼤值.设想,将 "前 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] + W i。
特殊的，当 v < C i时，可以认为当前的容量是放不下第 i 件物品的，即此时相当于不放第 i 件物品的价值F[i - 1][v].分析到这⾥则可得状态转移⽅程为: F[i][v] = v < C i F[i - 1][v] : max( F[i - 1][v], F[i - 1][v - C i] + W i ).在这⾥要特别的说明⼀下,这个⽅程⾮常重要,⼀定要知道这是怎么推出来的,⼏乎后⾯的所有的背包问题都和这个⽅程有着密不可分的联系.伪代码如下:F[0...N][0...V] <--- 0for i <--- 1 to N for v <--- C i to V F[i][v] = v < C i F[i - 1][v] : max( F[i - 1][v], F[i - 1][v - C i] + W i );具体代码:1void _01Pack(int F[][MAXV], int N, int V, int C[], int W[]){2 memset(F, 0, sizeof(F));3for(int i = 1; i <= N; i++) {4for(int v = 0; v <= V; v++) {5 F[i][v] = v < C[i] ? F[i - 1][v] : max(F[i - 1][v], F[i - 1][v - C[i]] + W[i]); //放或者不放两者之中选择最优者6 }7 }8 }三:优化空间复杂度 可以清楚的看到上⾯算法的时间复杂度和空间复杂度均为 O(N * V), 这⾥时间复杂度已经不能得到优化,但是空间复杂度确可以优化到O(V). 先看上⾯代码是如何实现的.最外⾯⼀层循环,每次计算出⼆维数组 F[i][0...V] 的值,计算的时候 F[i][0...V] 是由它的上⼀层 F[i - 1][0...V] ⽽得到的.那么如果把这个数组换成⼀维的 F[v] 那么还能保留上⼀次的状态吗.答案是可以的.由于动态规划算法的⽆后效性,第 i + 1 件物品的选择与否不会影响到第 i 件物品(即它的前⼀件物品)的选择状态.那么可以在上⾯第⼆次循环中按照 v <--- V...0 递减的顺序来计算 F[v], 这样计算F[v] 时所需要的状态 F[v] 和 F[v - C i] + W i 仍然还是上⼀次的状态.⽽计算 F[v] 之后, v 的顺序是递减的, F[v] 不会影响到 F[v'] (v' < v), 因为F[v']只与 F[v'](上⼀次的值) 和 F[v - C i] 有关, ⽽ F[v] > F[v'] > F[v' - C i]. 所以⼜可得状态转移⽅程. F[v] = max( F[v], F[v - C i] + W i ).伪代码如下:F[0...V] <--- 0for i <--- 1 to N for v <--- V to C i F[v] = max( F[v], F[v - C i] + W i );具体代码:1void _01Pack(int F[], int N, int V, int C[], int W[]){2 memset(F, 0, sizeof(F));3for(int i = 1; i <= N; i++) {4for(int v = V; v >= C[i]; v--) {5 F[i][v] = max(F[v], F[v - C[i]] + W[i]);6 }7 }8 }可以看到从第⼀个状态转移⽅程到第⼆个状态转移⽅程的空间优化效率还是挺⼤的: F[i][v] = max( F[i - 1][v], F[i - 1][v - C i] + W i ). ----> F[v] = max( F[v], F[v - C i] + W i ).在第⼆个⽅程中 F[v]1 = max(F[v]2, F[v - C i] + W i), 其实 F[v]2 就相当与⽅程⼀中的 F[i - 1][v], 对应的 F[v - C i] + W i就相当于 F[i -1][v - C i] + W i.这⼀正确性是在内层循环递减的前提下才成⽴的.否则, 将内层循环改为递增, 那么 F[i][v] 其实是由 F[i][v] 和 F[i][v - C i] 推出来的,这不符合基本思路中的探讨.之前说过由于 01背包的特殊性,这⾥将 01背包抽象化,⽅便之后的调⽤.解决单个物品 01背包的伪代码:def ZeroOnePack (F, C, W) for v <--- V to C F[v] = max( F[v], F[v - C] + W );这么写之后, 01背包总问题解决的伪代码就可以改写成:F[0...V] <--- 0for i <--- 1 to N ZeroOnePack(F, C[i], W[i]);具体代码:1const int MAXN = 10000;2int N, V, C[MAXN], W[MAXN];34void ZeroOnePack(int F[], int C, int W) { // 对于单个物品的决策5for(int v = V; v >= C; v--) {6 F[v] = max(F[v], F[v- C] + W);7 }8 }910void solv(int F[]) {11 memset(F, 0, sizeof(F));12for(int i = 1; i <= V; i++) {13 ZeroOnePack(F, C[i], W[i]);14 }15 }四: 01背包问题的拓展 ------ 初始化的细节问题 在上述 01背包的问题中,仅问得是 “如何选取,才能使的最后的总价值最⼤”, 这⾥并没有规定是否必须装满背包, 但是有的题将会给予这个附加条件, 即“在要求恰好装满背包的前提下, 如何选取物品, 才能使的最后的总价值最⼤ ”. 这两种问法, 在代码实现上相差⽆⼏.如果是上述问法,要求 “恰好装满背包”, 那么在初始化时除了将 F[0] 赋值为 0 之外, 其他的 F[1...V] 都应该赋值为 -∞,这样就可以保证最后的得到的 F[V] 是⼀种恰好装满背包的最优解.如果没有要求必须把背包装满,⽽是只希望价值尽量最⼤,初始化时应该将F[0...V] 全部设置为 0. 之所以可以这么做,是因为初始化的 F[] 事实就是没有任何物品放⼊背包时的合法状态.如果要求背包恰好装满,那么只有容量为 0 的背包在什么也不装且价值为 0 的情况下被装 "恰好装满",其他容量的背包如果不装物品, 那么默认的情况下都是不合法状态,应该被赋值为 -∞, 即对于第⼀个物品⽽⾔, 其合法状态只能由 F[0] 转移得到.如果背包并⾮必须被装满,那么任何容量的背包在没有物品可装时都存在⼀个合法解,即什么都不装,且这个解的价值为 0.所以将其全部初始化为 0 是可以的. 注:这个技巧完全可以拓展到其他背包问题中.伪代码:def ZeroOnePack (F, C, W) for v <--- V to C F[v] = max( F[v], F[v - C] + W )end defdef slov() F[0] = 0, F[1...V] <--- -∞ for i <--- 1 to N ZeroOnePack(F, C[i], W[i])end def具体代码:1const int MAXN = 10000;2int N, V, C[MAXN], W[MAXN];34void ZeroOnePack(int F[], int C, int W) {5for(int v = V; v >= C; v--) {6 F[v] = max(F[v], F[v- C] + W);7 }8 }910void solv(int F[]) {11 F[0] = 0;12for(int i = 1; i <= V; i++) F[i] = INT_MIN; // 除F[0] = 0之外, 其他全部赋值为负⽆穷13for(int i = 1; i <= V; i++) {14 ZeroOnePack(F, C[i], W[i]);15 }16 }五:⼀个常数级别的优化上述伪代码的:for i <--- 1 to N for v <--- V to C i可以优化为:for i <--- 1 to N for v <--- V to max( V - SUM(i...N)C i, C i)。
背包它是在1978年由Merkel和He llman提出的。
它的主要思路是假定某人拥有大量物品，重量各不同。
此人通过秘密地选择一部分物品并将它们放到背包中来加密消息。
背包中的物品中重量是公开的，所有可能的物品也是公开的，但背包中的物品是保密的。
附加一定的限制条件，给出重量，而要列出可能的物品，在计算上是不可实现的。
背包问题是熟知的不可计算问题，背包体制以其加密，解密速度快而其人注目。
但是，大多数一次背包体制均被破译了，因此现在很少有人使用它。
DD牛的背包九讲P01: 01背包问题题目有N件物品和一个容量为V的背包。
第i件物品的费用是c，价值是w。
求解将哪些物品装入背包可使这些物品的费用总和不超过背包容量，且价值总和最大。
基本思路这是最基础的背包问题，特点是：每种物品仅有一件，可以选择放或不放。
用子问题定义状态：即f[v]表示前i件物品恰放入一个容量为v的背包可以获得的最大价值。
则其状态转移方程便是：f[v]=max{f[v],f[v-c]+w}。
这个方程非常重要，基本上所有跟背包相关的问题的方程都是由它衍生出来的。
所以有必要将它详细解释一下：“将前i件物品放入容量为v的背包中”这个子问题，若只考虑第i 件物品的策略（放或不放），那么就可以转化为一个只牵扯前i-1件物品的问题。
如果不放第i件物品，那么问题就转化为“前i-1件物品放入容量为v的背包中”；如果放第i件物品，那么问题就转化为“前i-1件物品放入剩下的容量为v-c的背包中”，此时能获得的最大价值就是f [v-c]再加上通过放入第i件物品获得的价值w。
注意f[v]有意义当且仅当存在一个前i件物品的子集，其费用总和为v。
所以按照这个方程递推完毕后，最终的答案并不一定是f[N] [V]，而是f[N][0..V]的最大值。
如果将状态的定义中的“恰”字去掉，在转移方程中就要再加入一项f[v-1]，这样就可以保证f[N] [V]就是最后的答案。
至于为什么这样就可以，由你自己来体会了。
优化空间复杂度以上方法的时间和空间复杂度均为O(N*V)，其中时间复杂度基本已经不能再优化了，但空间复杂度却可以优化到O(V)。
先考虑上面讲的基本思路如何实现，肯定是有一个主循环i=1..N，每次算出来二维数组f[0..V]的所有值。
那么，如果只用一个数组f [0..V]，能不能保证第i次循环结束后f[v]中表示的就是我们定义的状态f[v]呢？f[v]是由f[v]和f [v-c]两个子问题递推而来，能否保证在推f[v]时（也即在第i次主循环中推f[v]时）能够得到f[v]和f[v -c]的值呢？事实上，这要求在每次主循环中我们以v=V..0的顺序推f[v]，这样才能保证推f[v]时f[v-c]保存的是状态f[v-c]的值。
伪代码如下：for i=1..Nfor v=V..0f[v]=max{f[v],f[v-c]+w};其中的f[v]=max{f[v],f[v-c]}一句恰就相当于我们的转移方程f[v]=max{f[v],f[v-c]}，因为现在的f[v-c]就相当于原来的f[v-c]。
如果将v的循环顺序从上面的逆序改成顺序的话，那么则成了f[v]由f[v-c]推知，与本题意不符，但它却是另一个重要的背包问题P02最简捷的解决方案，故学习只用一维数组解01背包问题是十分必要的。
总结01背包问题是最基本的背包问题，它包含了背包问题中设计状态、方程的最基本思想，另外，别的类型的背包问题往往也可以转换成01背包问题求解。
故一定要仔细体会上面基本思路的得出方法，状态转移方程的意义，以及最后怎样优化的空间复杂度。
P02: 完全背包问题题目有N种物品和一个容量为V的背包，每种物品都有无限件可用。
第i种物品的费用是c，价值是w。
求解将哪些物品装入背包可使这些物品的费用总和不超过背包容量，且价值总和最大。
基本思路这个问题非常类似于01背包问题，所不同的是每种物品有无限件。
也就是从每种物品的角度考虑，与它相关的策略已并非取或不取两种，而是有取0件、取1 件、取2件……等很多种。
如果仍然按照解01背包时的思路，令f[v]表示前i种物品恰放入一个容量为v的背包的最大权值。
仍然可以按照每种物品不同的策略写出状态转移方程，像这样：f[v]=max{f[v-k*c]+k*w|0<=k*c& lt;= v}。
这跟01背包问题一样有O(N*V)个状态需要求解，但求解每个状态的时间则不是常数了，求解状态f[v]的时间是O(v/c)，总的复杂度是超过O(VN)的。
将01背包问题的基本思路加以改进，得到了这样一个清晰的方法。
这说明01背包问题的方程的确是很重要，可以推及其它类型的背包问题。
但我们还是试图改进这个复杂度。
一个简单有效的优化完全背包问题有一个很简单有效的优化，是这样的：若两件物品i、j满足c<=c[j]且w>=w[j]，则将物品j去掉，不用考虑。
这个优化的正确性显然：任何情况下都可将价值小费用高得j换成物美价廉的i，得到至少不会更差的方案。
对于随机生成的数据，这个方法往往会大大减少物品的件数，从而加快速度。
然而这个并不能改善最坏情况的复杂度，因为有可能特别设计的数据可以一件物品也去不掉。
转化为01背包问题求解既然01背包问题是最基本的背包问题，那么我们可以考虑把完全背包问题转化为01背包问题来解。
最简单的想法是，考虑到第i种物品最多选V/c 件，于是可以把第i种物品转化为V/c件费用及价值均不变的物品，然后求解这个01背包问题。
这样完全没有改进基本思路的时间复杂度，但这毕竟给了我们将完全背包问题转化为01背包问题的思路：将一种物品拆成多件物品。
更高效的转化方法是：把第i种物品拆成费用为c*2^k、价值为w*2^k 的若干件物品，其中k满足c*2^k<V。
这是二进制的思想，因为不管最优策略选几件第i种物品，总可以表示成若干个2^k件物品的和。
这样把每种物品拆成O(log(V/c))件物品，是一个很大的改进。
但我们有更优的O(VN)的算法。
* O(VN)的算法这个算法使用一维数组，先看伪代码：<pre class"example"> for i=1..N for v=0..V f[v]=max{f[v],f[v-c]+w};你会发现，这个伪代码与P01的伪代码只有v的循环次序不同而已。
为什么这样一改就可行呢？首先想想为什么P01中要按照v=V..0的逆序来循环。
这是因为要保证第i次循环中的状态f[v]是由状态f[v-c]递推而来。
换句话说，这正是为了保证每件物品只选一次，保证在考虑“选入第i件物品”这件策略时，依据的是一个绝无已经选入第i件物品的子结果f[v-c]。
而现在完全背包的特点恰是每种物品可选无限件，所以在考虑“加选一件第i种物品”这种策略时，却正需要一个可能已选入第i种物品的子结果f[v-c]，所以就可以并且必须采用v= 0..V的顺序循环。
这就是这个简单的程序为何成立的道理。
这个算法也可以以另外的思路得出。
例如，基本思路中的状态转移方程可以等价地变形成这种形式：f[v]=max{f[v],f[v-c]+w}，将这个方程用一维数组实现，便得到了上面的伪代码。
总结完全背包问题也是一个相当基础的背包问题，它有两个状态转移方程，分别在“基本思路”以及“O(VN)的算法“的小节中给出。
希望你能够对这两个状态转移方程都仔细地体会，不仅记住，也要弄明白它们是怎么得出来的，最好能够自己想一种得到这些方程的方法。
事实上，对每一道动态规划题目都思考其方程的意义以及如何得来，是加深对动态规划的理解、提高动态规划功力的好方法。
P03: 多重背包问题题目有N种物品和一个容量为V的背包。
第i种物品最多有n件可用，每件费用是c，价值是w。
求解将哪些物品装入背包可使这些物品的费用总和不超过背包容量，且价值总和最大。
基本算法这题目和完全背包问题很类似。
基本的方程只需将完全背包问题的方程略微一改即可，因为对于第i 种物品有n+1种策略：取0件，取1件……取n件。
令f[v]表示前i种物品恰放入一个容量为v的背包的最大权值，则：f[v]=max{f[v-k*c]+ k*w|0<=k<=n}。
复杂度是O(V*∑n)。
转化为01背包问题另一种好想好写的基本方法是转化为01背包求解：把第i种物品换成n件01背包中的物品，则得到了物品数为∑n的01背包问题，直接求解，复杂度仍然是O(V*∑n)。
但是我们期望将它转化为01背包问题之后能够像完全背包一样降低复杂度。
仍然考虑二进制的思想，我们考虑把第i种物品换成若干件物品，使得原问题中第i种物品可取的每种策略——取0..n件——均能等价于取若干件代换以后的物品。
另外，取超过n件的策略必不能出现。
方法是：将第i种物品分成若干件物品，其中每件物品有一个系数，这件物品的费用和价值均是原来的费用和价值乘以这个系数。
使这些系数分别为1,2,4,...,2^(k-1),n-2^k+1，且k是满足n-2^k+1>0的最大整数。
例如，如果n为13，就将这种物品分成系数分别为1,2,4,6的四件物品。
分成的这几件物品的系数和为n，表明不可能取多于n件的第i种物品。
另外这种方法也能保证对于0..n间的每一个整数，均可以用若干个系数的和表示，这个证明可以分0..2^k-1和2^k..n两段来分别讨论得出，并不难，希望你自己思考尝试一下。
这样就将第i种物品分成了O(log n)种物品，将原问题转化为了复杂度为O(V*∑log n)的01背包问题，是很大的改进。
O(VN)的算法多重背包问题同样有O(VN)的算法。
这个算法基于基本算法的状态转移方程，但应用单调队列的方法使每个状态的值可以以均摊O(1)的时间求解。
由于用单调队列优化的DP 已超出了NOIP的范围，故本文不再展开讲解。
我最初了解到这个方法是在楼天成的“男人八题”幻灯片上。
小结这里我们看到了将一个算法的复杂度由O(V*∑n)改进到O(V*∑log n)的过程，还知道了存在应用超出NOIP范围的知识的O(VN)算法。
希望你特别注意“拆分物品”的思想和方法，自己证明一下它的正确性，并用尽量简洁的程序来实现。
P04: 混合三种背包问题问题如果将P01、P02、P03混合起来。
也就是说，有的物品只可以取一次（01背包），有的物品可以取无限次（完全背包），有的物品可以取的次数有一个上限（多重背包）。
应该怎么求解呢？目录[隐藏]∙ 1 定义∙ 2 计算复杂度∙ 3 动态规划解法o 3.1 无界背包问题o 3.2 0-1背包问题∙ 4 二次背包问题∙ 5 外部链接[编辑]定义我们有n种物品，物品j的重量为w j，价格为p j。
我们假定所有物品的重量和价格都是非负的。
