一. 01背包问题
01背包是取出m个物品放入空间w的背包中，各物品的体积为C1、C2、…、Cn，相应的价值为W1、W2、…、Wn。 解开把那些物品放进背包，总价值就最大了。
动态规划：
1 )子问题的定义： F[i][j]表示从最初的I个物品中选择几个物品，剩下的空间放入j的背包中得到的最大价值。
2 )根据放置还是不放置第I件物品而定
其中F[i-1][j]表示从最初的i-1个物品中选择几个物品，剩下的空间放入j的背包中得到的最大价值；
另一方面，F[i-1][j-C[i]] W[i]在通过从最初的i-1个物品中选择几个物品并将剩下的空间放入j-C[i]的背包中而得到的最大价值上加上第I个物品的价值
根据放置还是不放置第I个物品，决定遍历第I个物品时的状态F[i][j]。
设项数为n，背包容量为v，第I个项目的体积为C[i]，第I个项目的价值为W[i]。
从这里写伪代码如下。
1 F[0][] {0}2
3 F[][0] {0}4
5 for i1to N6
7 do for k1to V8
9 F[i][k] F[i-1][k]10
11if(k=c[I] ) 12
13thenf[I][k]max(f[I][k]，F[i-1][k-C[i]] W[i] ) 14
15 return F[N][V]
上面的代码9-13行也可以这样写：
if(k
then F[i][k] F[i-1][k]
elseF[i][k] max(F[i-1][k]，F[i-1][k-C[i]] W[i]
如果第I个物品的体积大于背包的剩余容量，则第I个物品一定放不下，所以F[i][k]=F[i-1][k]，
另一方面，在第I个物品的体积为背包的剩余容量以下的情况下，有放入或不放入第I个物品F[i-1][k-C[i]] W[i]这两个选择，在两者之间是最优先的
编写第一个等效伪代码是为了更好地理解二维数组解法到一维数组解法的转换。
通过算法获得的最大价值表本身实际上包括位置信息，从F[N][V]相反地朝向F[0][0]，i=N，j=V，f [ I ] [ j ]==f [ I-1 ]
打印背包内物品的伪代码如下。
1 iN2
3 jV4
5while(I0J0) 6
7 doif (f [ I ] [ j ]=f [ I-1 ] [ j-c [ I ] ] w [ I ] ) 8
9 then Print W[i]10
11 jj-C[i]12
13 ii-1
定义存储背包中物品信息的二维阵列Path[N][V]，开始时Path[N][V]初始化为0，F[i][j]==F[i-1][j-C[i]] W[i]的这里，Path[0][]和Path[][0]是边界。
添加路径信息的伪代码如下。
F[0][] {0}
F[][0] {0}
Path[][] 0
for i1to Ndo for k1to V
f [ I ] [ k ]f [ I-1 ] [ k ] if (k=c [ I ] f [ I ] [ k ] f [ I-1 ] [ k-c [ I ] ] w [ I ]
then F[i][k] F[i-1][k-C[i]] W[i]
Path[i][k] 1
return F[N][V] and Path[][]
打印背包内物品的伪代码如下。
iN
jV
是wile(I0J0)
doif(path[I][j]=1) () ) ) ) ) ) ) )。
then Print W[i]
jj-C[i]
ii-1
将2位数组的使用更改为一维数组的使用：
即使查看伪代码，也可以看到F[i][j]只与F[i-1][j]和F[i-1][j-C[i]]有关。 也就是说，由于只与i-1时刻的状态有关，所以需要以一维数组F[]保存i-1时的状态F[]。 设i-1时刻的F[]为{a0，a1，a2，…，av}，则I时刻的F[]中第k个是max(ak，ak-C[i] W[i]即max(F[k]，f [ k-c ] )
证求i时刻F[k]时F[k-C[i]]是i-1时刻的值。如果正序遍历则当求F[k]时其前面的F[0],F[1]，…，F[K-1]都已经改变过，里面存的都不是i-1时刻的值，这样求F[k]时利用F[K-C[i]]必定是错的值。最后F[V]即为最大价值。求F[j]的状态方程如下：
伪代码如下：
1 F[] ← {0}2
3 for i ← 1to N4
5 do fork ← V to C[i]6
7 F[k] ← max(F[k],F[k-C[i]]+W[i])8
9 return F[V]
加入路径信息的伪代码如下：
1 F[] ← {0}2
3 Path[][]←0
4
5 for i←1to N6
7 do fork←V to C[i]8
9 if(F[k] < F[k-C[i]]+W[i])10
11 then F[k] ← F[k-C[i]]+W[i]12
13 Path[i][k] ← 1
14
15 return F[V] and Path[][]
二、物品无限的背包问题
将01背包一维数组解法中j的遍历顺序do for k←V to C[i]改为do for k←C[i] to V就变成了物品无限背包的解法。
1 F[] ← {0}2
3 for i ← 1to N4
5 do fork ← C[i] to V6
7 F[k] ← max(F[k],F[k-C[i]]+W[i])8
9 return F[V]
三、完全背包(要求背包必须装满，而不是最大限度的装)
主要是在01背包的初始化过程中的不同，然后考虑第i个物体的时候判断下是否可以装满的条件
1 F[][] ← {-1}2
3 F[][0] ← {0}4
5 for i←1to N6
7 do for k←1to V8 if (F[i-1][k-C[i]]!=-1)9 then10
11 F[i][k] ← F[i-1][k]12
13 if(k >=C[i])14
15 then F[i][k] ← max(F[i][k],F[i-1][k-C[i]]+W[i])16
17 return F[N][V]
四、代码实际操练：
二维数组解法：
01背包问题具体例子：先输入两个数n,V表示物品的个数和背包的容量，接下来输入n组数据代表n种物品，每组数据有两个值对应物品的体积和价值，每种物品只有一个，求在背包容量下能装物品最大价值，并求出最大价值下，组合中各个物品的价值？
#include
using namespacestd;const int N_max=100;//物品个数上限
const int V_max=100;//背包容量上限
intdp[N_max][V_max];boolflag[N_max][V_max];intmain()
{int n;//实际输入物品的个数
cin>>n;int V;//背包的实际容量
cin>>V;int *v=new int[n+1];int *price=new int[n+1];//输入n组数据，分别为体积v和价值price//注意这里要从1开始
for(int i=1;i<=n;i++)
{
cin>>v[i]>>price[i];
}//初始化dp数组//注意这里的=
for(int i=0;i<=n;i++)
{
dp[i][0]=0;
}for(int i=0;i<=V;i++)
{
dp[0][i]=0;
}//初始化flag数组
memset(flag,false,(n+1)*(V+1)*sizeof(bool));//开始递推
for(int i=1;i<=n;i++)
{for(int j=1;j<=V;j++)
{
dp[i][j]=dp[i-1][j];if(v[i]<=j && dp[i-1][j-v[i]]+price[i]>dp[i][j])//放下该物品
{
dp[i][j]=dp[i-1][j-v[i]]+price[i];
flag[i][j]=true;
}
}
}
cout<
cout<=0 && j>=0)
{if(flag[i][j])
{
cout<
j=j-v[i];
}
i--;
}return 0;
}
一维数组的解法：
#include
using namespacestd;bool flag[100][100]={false};intmain()
{int n;//实际输入物品的个数
cin>>n;int V;//背包的实际容量
cin>>V;int *dp=new int[V+1];int *v=new int[n+1];int *price=new int[n+1];//输入n组数据，分别为体积v和价值price//注意这里要从1开始
for(int i=1;i<=n;i++)
{
cin>>v[i]>>price[i];
}//初始化dp数组
memset(dp,0,(V+1)*sizeof(int));//开始递推
for(int i=1;i<=n;i++)
{for(int j=V;j>=v[i];j--)//for(int j=v[i];j<=V;j++)
{if( dp[j-v[i]]+price[i]>dp[j])//放下该物品
{
dp[j]=dp[j-v[i]]+price[i];
flag[i][j]=true;
}
}
}
cout<
cout<=0 && j>=0)
{if(flag[i][j])
{
cout<
j=j-v[i];
}
i--;
}return 0;
}
调试结果：
物品无限背包问题具体例子：先输入两个数n,V表示物品的个数和背包的容量，接下来输入n组数据代表n种物品，每组数据有两个值对应物品的体积和价值，每种物品有无限个，求在背包容量下能装物品最大价值，并求出最大价值下，组合中各个物品的价值？
#include#include#include
using namespacestd;bool flag[100][100]={false};intmain()
{int n;//实际输入物品的个数
cin>>n;int V;//背包的实际容量
cin>>V;int *dp=new int[V+1];int *v=new int[n+1];int *price=new int[n+1];//输入n组数据，分别为体积v和价值price//注意这里要从1开始
for(int i=1;i<=n;i++)
{
cin>>v[i]>>price[i];
}//初始化dp数组
memset(dp,0,(V+1)*sizeof(int));//开始递推
for(int i=1;i<=n;i++)
{for(int j=v[i];j<=V;j++)
{if( dp[j-v[i]]+price[i]>dp[j])//放下该物品
{
dp[j]=dp[j-v[i]]+price[i];
flag[i][j]=true;
}
}
}
cout<
}
01背包下恰好装满的例子：先输入两个数n,V表示物品的个数和背包的容量，接下来输入n组数据代表n种物品，每组数据有两个值对应物品的体积和价值，每种物品只有一个，求在背包恰好装满时物品最大价值，并求出最大价值下，组合中各个物品的价值，若无法恰好装满，则输出无法装满的提示语句？
#include
using namespacestd;const int N_max=100;//物品个数上限
const int V_max=100;//背包容量上限
intdp[N_max][V_max];boolflag[N_max][V_max];intmain()
{int n;//实际输入物品的个数
cin>>n;int V;//背包的实际容量
cin>>V;int *v=new int[n+1];int *price=new int[n+1];//输入n组数据，分别为体积v和价值price//注意这里要从1开始
for(int i=1;i<=n;i++)
{
cin>>v[i]>>price[i];
}//注意恰好装满与普通01背包的初始化条件是不同的
memset(dp,-1,sizeof(dp));for(int i=0;i<=n;i++)
{
dp[i][0]=0;
}//初始化flag数组
memset(flag,false,(n+1)*(V+1)*sizeof(bool));//开始递推
for(int i=1;i<=n;i++)
{for(int j=1;j<=V;j++)
{//注意这里是恰好装满时的判断条件
if(dp[i-1][j-v[i]]!=-1)
{
dp[i][j]=dp[i-1][j];if(v[i]<=j && dp[i-1][j-v[i]]+price[i]>dp[i][j])//放下该物品
{
dp[i][j]=dp[i-1][j-v[i]]+price[i];
flag[i][j]=true;
}
}
}
}if(dp[n][V]==-1)
{
cout<
}else{
cout<
cout<=0 && j>=0)
{if(flag[i][j])
{
cout<
j=j-v[i];
}
i--;
}
}return 0;
}