完全背包是在N种物品中选取若干件（同一种物品可多次选取）放在空间为V的背包里，每种物品的体积为C1，C2，…，Cn，与之相对应的价值为W1,W2，…，Wn.求解怎么装物品可使背包里物品总价值最大。

Fk(y):只装前 k 种物品,  总重不超过 y,  背包的最大价值
ik(y):只装前 k 种物品,  总重不超过 y,  背包达最大价值时装入物品的最大标号

递推方程和边界条件如下：
Fk(y)=max{Fk-1(y),Fk(y-wk)+vk}     max{不装第k种物品，至少一个k种物品}
F0(y)=0        0<=y<=b
Fk(0)=0        0<=k<=n
F1(y)=[y/w1]v1    只装第一种物品，总重量不超过y,[ ]向下取整
Fk(y)=-∞    y<0    设定边界值

标记函数ik(y)

ik(y)=ik-1(y)    Fk-1(y)>Fk(y-wk)+vk
ik(y)=k         Fk-1(y)<=Fk(y-wk)+vk

v1 = 1,   v2 = 3,  v3 = 5,  v4 = 9,
w1 = 2,   w2 = 3,  w3 = 4,  w4 = 7,
b = 10

只挑前1种物品的价值情况：
F1(0)=0
F1(1)=0      i1(1)=0
F1(2)=1      i1(2)=1
F1(3)=1      i1(3)=1
F1(4)=2      i1(4)=1
F1(5)=2      i1(5)=1
F1(6)=3      i1(6)=1
F1(7)=3      i1(7)=1
F1(8)=4      i1(8)=1
F1(9)=4         i1(9)=1
F1(10)=5     i1(10)=1

只挑前2种物品的价值情况：
F2(2-w2)+v2:  总重量为2-w2的情况下,只装前2种物品最大价值与第2种物品的价值和
F2(0)=0
F2(1)=max{F1(1),F2(1-w2)+v2}=max{0,-∞+3}=0                                        i2(1)=0

F2(2)=max{F1(2),F2(2-w2)+v2}=max{1,-∞+3}=1                            i2(2)=i1(2)=1

F2(3)=max{F1(3),F2(3-w2)+v2}=max{1,0+3}=3                          i2(3)=2

F2(4)=max{F1(4),F2(4-w2)+v2}=max{2,F2(4-3)+3}=max{2,F2(1)+3}=max{2,0+3}=3          i2(4)=2

F2(5)=max{F1(5),F2(5-w2)+v2}=max{2,F2(5-3)+3}=max{2,F2(2)+3}=max{2,1+3}=4    i2(5)=2

F2(6)=max{F1(6),F2(6-w2)+v2}=max{3,F2(6-3)+3}=max{3,F2(3)+3}=max{3,3+3}=6    i2(6)=2  （接着考虑i2(6-3))

F2(7)=max{F1(7),F2(7-w2)+v2}=max{3,F2(7-3)+3}=max{3,F2(4)+3}=max{3,3+3}=6    i2(7)=2     （接着考虑i2(7-3))

F2(8)=max{F1(8),F2(8-w2)+v2}=max{3,F2(8-3)+3}=max{3,F2(5)+3}=max{3,4+3}=7    i2(8)=2     （接着考虑i2(8-3))

F2(9)=max{F1(9),F2(9-w2)+v2}=max{3,F2(9-3)+3}=max{3,F2(6)+3}=max{3,6+3}=9    i2(9)=2     （接着考虑i2(9-3))
.......

F3(2)=max{F2(2),F3(2-w3)+v3}=max{1,F3(2-4)+5}=1                    i3(2)=1
...........

只挑前3种物品的价值情况：
F3(0)=0

F3(1)=max{F2(1),F3(1-w3)+v3}=max{0,-∞+5}=0                                        i3(1)=0

F3(2)=max{F2(2),F3(2-w3)+v3}=max{1,-∞+5}=1                                        i3(2)=i2(2)=i1(2)=1

F3(3)=max{F2(3),F3(3-w3)+v3}=max{3,-∞+5}=3                                        i3(3)=i2(3)=2

F3(4)=max{F2(4),F3(4-w3)+v3}=max{F2(4),F3(0)+v3}=max{3,0+5}=5               i3(4)=3

F3(5)=max{F2(5),F3(5-w3)+v3}=max{F2(5),F3(1)+v3}=max{4,0+5}=5               i3(5)=3

F3(6)=max{F2(6),F3(6-w3)+v3}=max{F2(6),F3(2)+v3}=max{6,1+5}=6               i3(6)=3   (把条件改成Fk-1(y)>=Fk(y-wk)+vk时 ik(y)=ik-1(y)   取最大物品的标号就会改变i3(6)=i2(6)=2  即只取前3种物品，总重量不超过6的情况下：会变成取两个2号物品)

.......................

一直要算到F4(10)的值           i4(10)

v1 = 2,   v2 = 4,  v3 = 2,  v4 = 1,  v5 = 10
w1 = 2,   w2 =12,  w3 = 1,  w4 = 1,  w5 = 4
b = 15

作业要求：
用户输入物品的数量，再输入每个物品价值与重量，再输入背包的总重量。(最好以数组直接定义的方式给出，免得输入数据。

代码如下：

#include <iostream>
#include <stdio.h>
using namespace std;
int v[1000]={0,1,3,5,9},w[1000]={0,2,3,4,7};//v存储价值，w存储重量 
//int v[1000]={0,2,4,2,1,10},w[1000]={0,2,12,1,1,4};//测试数据2 
int F[1000][1000]={0},i[1000][1000]={0},x[1000]={0};//优化函数F[k][y]，代表只允许装前k种物品的最大价值 
void recall(int N,int B)//应用递归算法回溯输出实例的解
{int rank=1;//设置行数为第1行 while(N)//当N为0时，追溯结束 {if(rank>1)//当行数rank大于1行时 {cout<<'i'<<N<<'('<<B<<"-w"<<N<<")=";//输出iN(B-w[N]) B-=w[N];//B=B-wN }cout<<'i'<<N<<'('<<B<<")="<<i[N][B]<<"-> ";//输出iN(B)=i[N][B]-> x[i[N][B]]++;//x[i[N][B]]加一 if(i[N][B]) cout<<'x'<<i[N][B]<<">="<<x[i[N][B]]<<',';//输出x[i[N][B]]>=x[i[N][B]]for(int t=N;t>i[N][B];t--)cout<<'x'<<t<<'='<<x[t]<<',';//输出i[N][B]+1到N-1的数据 N=i[N][B];//N=i[N][B]rank++;	//行数加一 cout<<endl;//换行 }}
void bag(int n,int b)//执行函数装包 
{for(int k=1;k<=n;k++)//只允许装前k种物品 {for(int y=1;y<=b;y++){if(k==1)//当只允许装第一种物品时，F1[y]=y/w1*v1 {F[1][y]=y/w[1]*v[1];//在背包足够时尽可能装多 if(w[1]<=y) i[1][y]=1;//如果第一种物品装得下，则i1[y]记录放下1号物品 else i[1][y]=0;//如果第一种物品装不下，则i1[y]设为0printf("F%d(%d)=%d     i%d(%d)=%d\n",k,y,F[k][y],k,y,i[k][y]);//格式输出 }else{if(w[k]<=y&&F[k-1][y]<=F[k][y-w[k]]+v[k]){//max{Fk[y],Fk[y-wk]+vk}F[k][y]=F[k][y-w[k]]+v[k];//Fk[y]=F[k][y-w[k]]+v[k]i[k][y]=k;//ik[y]记录放入k号物品 }else{F[k][y]=F[k-1][y];//Fk[y]=F[k][y-w[k]]+v[k]i[k][y]=i[k-1][y];//ik[y]记录放入i[k-1][y]号物品}//按格式输出步骤 printf("F%d(%d)=max{F%d(%d),F%d(%d-w%d)+v%d}=",k,y,k-1,y,k,y,k,k);//输出 printf("max{%d,F%d(%d-%d)+%d}=",k,k,y,w[k],v[k]);//输出 cout<<"max{"<<F[k-1][y]<<',';if(w[k]>y) cout<<"-∞";//如果wk>y，则Fk(y-wk)=-∞else cout<<F[k][y-w[k]];//否则输出数字 cout<<'+'<<v[k]<<"}="<<F[k][y];cout<<"     i"<<k<<'('<<y<<")=";if(w[k]>y||F[k-1][y]>F[k][y-w[k]]+v[k]) cout<<'i'<<k-1<<'('<<y<<")=";cout<<i[k][y]<<endl;//输出ik(y)}}cout<<endl;}cout<<"得出可装入物品的最大价值为"<<F[n][b]<<endl;cout<<"追踪解的过程:"<<endl;recall(n,b);//追踪解的过程函数cout<<"最终得到的实例解为："; for(int t=1;t<=n;t++){if(t==n)  cout<<'x'<<t<<'='<<x[t]<<'.'<<endl;//最后一个输出句号，换行 else  cout<<'x'<<t<<'='<<x[t]<<',';}}
int main()
{int n=4,b=10;//n代表物品总数，b代表背包容量//int n=5,b=15;//测试数据2 bag(n,b);//将物品总数n和背包容量b代入执行函数装包 
}

输出结果