转载： http://blog.csdn.net/dapengbusi/article/details/7463968
动态规划0-1背包问题
Ø
问题描述：
给定n种物品和一背包。物品i的重量是wi，其价值为vi，背包的容量为C。问应如何选择装入背包的物品，使得装
入背包中物品的总价值最大?
Ø
对于一种物品，要么装入背包，要么不装。所以对于一种物品的装入状态可以取0和1.我们设物品i的装入状态为xi,xi∈ (0,1)，此问题称为0-11背包问题。
过程分析
数据：物品个数n=5,物品重量w[n]={0，2，2，6，5，4},物品价值V[n]={0，6，3，5，4，6},
（第0位，置为0，不参与计算，只是便于与后面的下标进行统一，无特别用处，也可不这么处理。）总重量c=10.
Ø背包的最大容量为10，那么在设置数组m大小时，可以设行列值为6和11，那么，对于m(i,j)就表示可选物品为i…n背包容量为j(总重量)时背包中所放物品的最大价值。
在得到在给定总重量时可以获得的最大value后，如何得到具体该放入哪些物品？也就是构造最优解的过程：
下面是自己写的源码：
- #include<stdio.h>
- #include<stdlib.h>
- #include<iostream>
- #include<queue>
- #include<climits>
- #include<cstring>
- using namespace std;
- const int c = 10;
- const int w[] = {0,2,2,6,5,4};
- const int v[] = {0,6,3,5,4,6};
- const int n = sizeof(w)/sizeof(w[0]) - 1 ;
- int x[n+1];
- void package0_1(int m[][11],const int w[],const int v[],const int n)
- {
-
-
- for(int j = 0; j <= c; j++)
- if(j < w[n]) m[n][j] = 0;
- else m[n][j] = v[n];
-
-
- int i;
- for(i = n-1; i >= 1; i--)
- for(int j = 0; j <= c; j++)
- if(j < w[i])
- m[i][j] = m[i+1][j];
-
- else m[i][j] = m[i+1][j] > m[i+1][j-w[i]] + v[i]?
- m[i+1][j] : m[i+1][j-w[i]] + v[i];
- }
- void answer(int m[][11],const int n)
- {
- int j = c;
- int i;
- for(i = 1; i <= n-1; i++)
- if(m[i][j] == m[i+1][j]) x[i] = 0;
- else {
- x[i] = 1;
- j = j - w[i];
- }
- x[n] = m[i][j] ? 1 : 0;
- }
- int main()
- {
- int m[6][11]={0};
-
- package0_1(m,w,v,n);
- for(int i = 0; i <= 5; i++)
- {
- for(int j = 0; j <= 10; j++)
- printf("%2d ",m[i][j]);
- cout << endl;
- }
- answer(m,n);
- cout << "The best answer is:\n";
- for(int i = 1; i <= 5; i++)
- cout << x[i] << " ";
- system("pause");
- return 0;
- }
动态规划——背包问题
原文：http://www.cnblogs.com/litian0605/p/5296448.html
