01背包问题
题目描述
一个旅行者有一个最多能装m公斤的背包，现在有n中物品，每件的重量分别是W1、W2、……、Wn，每件物品的价值分别为C1、C2、……、Cn， 需要将物品放入背包中，要怎么样放才能保证背包中物品的总价值最大？
解题思路
动态规划方程
V(i,0)=V(0,j)=0
V(i,j)=V(i-1,j) jwi 能装下的时候，选择装不装
如果要到达V(i,j)这一个状态有几种方式？
第一种是第i件商品没有装进去，第二种是第i件商品装进去了。
没有装进去,就是V(i-1,j);如果装进去第i件商品，是V(i-1,j-w(i))
由于最优性原理,V(i-1,j-w(i))就是前面决策造成的一种状态，后面的决策就要构成最优策略。两种情况进行比较，得出最优。
具体代码实现
#include#includeint V[100][100];//前i个物品装入容量为j的背包中获得的最大价值
int max(int a,int b){
if(a>=b)
return a;
else return b;
}
int KnapSack(int n,int weight[],int value[],int C){
//填表,其中第一行和第一列全为0,即 V(i,0)=V(0,j)=0；
for(int i=0;i<=n;i++)
V[i][0]=0;
for(int j=0;j<=C;j++)
V[0][j]=0;
//用到的矩阵部分V[n][C] ,下面输出中并不输出 第1行和第1列
printf("编号 重量 价值 "); //菜单栏 1
for(int i=1;i<=C;i++)
printf(" %2d ",i);
printf("\n\n");
for(int i=1;i<=n;i++){
printf("%2d %2d %2d ",i,weight[i-1],value[i-1]); //菜单栏 2 (weight与value都是从0开始存的，所以开始i=1时对应0的位置)
for(int j=1;j<=C;j++){
if(j=1;i--){
if(V[i][j]>V[i-1][j]){ //如果装了就标记，然后减去相应容量
state[i]=1;
j=j-weight[i-1];
}
else
state[i]=0;
}
printf("选中的物品是:");
for(int i=1;i<=n;i++)
if(state[i]==1)
printf("%d ",i);
printf("\n");
}
int main(){
int n; //物品数量
int Capacity;//背包最大容量
printf("请输入背包的最大容量:");
scanf("%d",&Capacity);
printf("输入物品数:");
scanf("%d",&n);
int *weight=(int *)malloc(n*sizeof(int));//物品的重量
int *value=(int *)malloc(n*sizeof(int)); //物品的价值
printf("请分别输入物品的重量:");
for(int i=0;i