0/1背包问题-----动态规划实现

问题描述：一个背包容量为m（能装下m千克的物品），现有n中货源，第i种货源的重量为wi，利润为pi，求怎样收购能获得最大利润

本人采用递归方法解决问题

整体思想：对于每一件物品只考虑“选择与不选择”，选择的要求是背包能容下。最后选取利润较大的作为最终利润结果。

核心代码： max2=knap5(m1,ii)+p[i];  //当前背包容量m1大于第i件物品的重量，递归调用并将当前物品装入背包

源码：

include<stdio.h>
float w[2]={2,5},p[2]={3,4},n=2,m=5;
knap5(int m,int i){
    int m1=m;
    int ii=i;
float max1,max2,t;
if(i==0)
    return 0;
max1=knap5(m,i-1);   //无论m是否大于第i件物品不选取第i件物品时的递归关系
if(m1>=w[i]){
    m1=m1-w[i];
    ii-=1;
    max2=knap5(m1,ii)+p[i];   //当前背包容量m1大于第i件物品的重量，递归调用并将当前物品装入背包
}


if(max1>max2){
    t=max1;
}
else{
    t=max2;  // 取较大的价值装入背包
}
return(t);


}


void main(){
int s=0,i;
printf("%f  %f \n",m,n);//输出背包容量和物品种类
for(i=1;i<=n;i++){
   printf("%f  %f \n",w[i],p[i]); //输出每种物品的重量和价值
   s=s+w[i];
}


if(s<=m){
    printf("所有物品全部装入背包!");  //当所有物品总重量小于背包容量时，全部装入背包
    return ;
}
float mid3=knap5(m,n);
printf("max= %f",mid3);

}

运行截图：