Question

我需要用动态规划 解决0/1背包问题的程序请高手帮帮忙吧！

若以下回答无法解决问题，邀请你更新回答

Answer 1

#include<stdio.h>
#include<math.h>
#define MAX 100 /* 最多物品数*/
void conversion(int n,int b[MAX]){/*将n化为二进制形式，结果存放到数组b中*/
int i;
for(i=0;i<MAX;i++)
{
b[i]=n%2;
n=n/2;
if(n==0)break;
}
}
void main()
{
int i,j,n,b[MAX],temp[MAX];
float tw,maxv,w[MAX],v[MAX],temp_w,temp_v;
printf("please input n:\n");
scanf("%d",&n);
printf("please input tw:\n");
scanf("%d",&tw);
printf("please input the value of v[]:\n");
for(i=0;i<n;i++)
scanf("%f",&v[i]);
maxv=0;
for(i=0;i<pow(2,n-1);i++)/*穷举2**n个可能的选择，找出物品的最优选择*/
{
for(j=0;j<n;j++)
{
b[j]=0;
temp[j]=0;
}
conversion(i,b);
temp_w=0;
temp_v=0;
for(j=0;j<n;j++)
if(b[j]==1)
{
temp_w=temp_w+w[j];
temp_v=temp_v+v[j];
}
if((temp_w<=tw)&&(temp_v>maxv))
{
maxv=temp_v;
for(j=0;j<n;j++)
temp[j]=b[j];
}
}
printf("the max values is %.3f:\n",maxv);
printf("the selection is %f:\n");
for(j=0;j<n;j++)
printf("%d",b[j]);
getchar();

}

调试通过....