1、问题描述：
给定n种物品和一背包。物品i的重量是wi，其价值为vi，背包的容量为C。问:应如何选择装入背包的物品，使得装入背包中物品的总价值最大?
例子：数据：物品个数n=5,物品重量w[n]={0，2，2，6，5，4},物品价值V[n]={0，6，3，5，4，6}
下面是算法分析的过程：
其实这里就是选择装与不装的问题关键
（1）对于m[5][j]，当j=w[5]时，物品5可以放入背包，此时背包的价值为v[5]。得到结果如下表：
Wi012345678910V
| 2 |
1 |
|
|
|
|
|
|
|
|
|
|
|
6 |
| 2 |
2 |
|
|
|
|
|
|
|
|
|
|
|
3 |
| 6 |
3 |
|
|
|
|
|
|
|
|
|
|
|
5 |
| 5 |
4 |
|
|
|
|
|
|
|
|
|
|
|
4 |
| 4 |
5 |
0
|
0
|
0 |
0
|
6 |
6 |
6 |
6 |
6 |
6 |
6 |
6 |
（2）在物品5的基础上分析物品4， 当j
当j>=w[4]时，物品4要么放入要么不放入。当物品4放入背包后，对于物品4+1到n，能达到的最大价值为m[4+1][j-w[4]]+v[4]，故此时能达到的最大价值为m[4+1][j-w[4]]+v[4]
当物品4不放入背包时，能达到的最大价值为m[4+1][j]。最后比较放入与不放入情况下，两者的最大值取其大者，分析结果如上表的橙色：
文章图片
当W【4】>j时，则物品4不能放入，所以m（4，j）=m（5，j）且m（4，0--4）=m（5，0--4）
Wi012345678910V
| 2 |
1 |
0 |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
9 |
10 |
6 |
| 2 |
2 |
|
|
|
|
|
|
|
|
|
|
|
3 |
| 6 |
3 |
|
|
|
|
|
|
|
|
|
|
|
5 |
| 5 |
4 |
0
|
0 |
0 |
0 |
6 |
|
|
|
|
|
|
4 |
| 4 |
5 |
0
|
0
|
0 |
0
|
6 |
6 |
6 |
6 |
6 |
6 |
6 |
6 |
当j>=4时，对物品4要么放入要么不放入，最优值得选择标准应依据总价值，总价值高的作为最优值，例如m（4，5），如果w4不放入的时候，原值，总价值为m（4+1，5）=6； 当w4放入的时候，则配合其前边的最优值，即w4放入，使剩下物品最大容量为j-w4，则背包最大容量为m（4+1，j-w4）的值为0再加上v4，然后再与前面不放入的m（4+1，5）作比较，发现m（4+1，j-w4）=4
Wi012345678910V
| 2 |
1 |
|
|
|
|
|
|
|
|
|
|
|
6 |
| 2 |
2 |
|
|
|
|
|
|
|
|
|
|
|
3 |
| 6 |
3 |
|
|
|
|
|
|
|
|
|
|
|
5 |
| 5 |
4 |
0
|
0 |
0 |
0 |
6 |
6 |
6 |
6 |
6 |
10 |
10 |
4 |
| 4 |
5 |
0
|
0
|
0 |
0
|
6 |
6 |
6 |
6 |
6 |
6 |
6 |
6 |
最后得出结果为：
Wi012345678910V
【0--1背包问题（动态规划）】
| 2 |
1 |
0 |
0 |
6 |
6 |
9 |
9 |
12 |
12 |
15 |
15 |
15 |
6 |
| 2 |
2 |
0 |
0 |
3 |
3 |
6 |
6 |
9 |
9 |
9 |
10 |
11 |
3 |
| 6 |
3 |
0
|
0 |
0 |
0 |
6 |
6 |
6 |
6 |
6 |
10 |
11 |
5 |
| 5 |
4 |
0
|
0 |
0 |
0 |
6 |
6 |
6 |
6 |
6 |
10 |
10 |
4 |
| 4 |
5 |
0
|
0
|
0 |
0
|
6 |
6 |
6 |
6 |
6 |
6 |
6 |
6 |
- #include
- #include
- using namespace std;
- void Knapsack(int *v,int *w,int n,int c,int **m)
- {
- int jMax=min(w[n]-1,c);
///背包剩余量的上限(0~~w[n]-1)
- for(int i=0;
i<=jMax;
i++)
- {
- m[n][i]=0;
- }
- for(int j=w[n];
j<=c;
j++)///例如这里是当j>w[5]的时候，则装入该物品的价值
- {
- 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++)///当不能装入的时候
- {
- m[i][j]=m[i+1][j];
- }
- for(int 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[2][c],m[2][c-w[1]]+v[1]);
- }
- }
- void TraceBack(int **m,int *w,int c,int n,int *x)
- {
- for(int i=1;
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 c,n;
- cout<<"输入物品的总个数：";
- cin>>n;
- cout<
- cin>>c;
- int *w=new int[n];
- int *v=new int[n];
- int *x=new int[n];
- int **m=new int *[n];
- for(int i=1;
i<=n;
i++)
- {
- m[i]=new int[c];
- }
- cout<
- for(int i=0;
i<=n;
i++)///输入物品的重量（注意，一开始我是以下标为1开始的，所以这里我输入的时候，下标0应该输入的是0）
- {
- cin>>w[i];
- }
- cout<
- for(int i=0;
i<=n;
i++)///输入物品的价值（注意，一开始我是以下标为1开始的，所以这里我输入的时候，下标0应该输入的是0）
- {
- cin>>v[i];
- }
- cout<
- for(int i=1;
i<=n;
i++)
- {
- cout<
- }
- Knapsack(v,w, n,c,m);
- cout<
- TraceBack(m,w, c, n,x);
- cout<
- for(int i=1;
i<=n;
i++)
- {
- if(x[i]==1)
- cout<
- }
- return 0;
- }
运行结果如下：
文章图片
推荐阅读
