Question

用动态规划法解 0/1背包问题 要求用c语言编写程序原代码。

实验项目 0/1背包问题
1.实验题目
给定n种物品和一个容量为C的背包，物品i的重量是wi，其价值为vi，0/1背包问题是如何选择装入背包的物品(物品不可分割)，使得装入背包中物品总价值最大。
2.实验要求
(1)设计动态规划法的填表过程和求解方法；
(3)设计测试数据，并讨论所得结果。

Answer 1

1.动态规划#include<stdio.h>
#include<stdlib.h>
#include<time.h>#define N 100 //货物的种类
#define M 10 //货物的质量（千克）typedef struct good
{
int no; //第几个物品
int w; //质量
int p; //可获利
int flag;
float pw; //获得的最高利润
}Good;void initGoodSet(Good a[],int n,int m);
int planning(Good a[], int m,int n); //动态规划void initGoodSet(Good a[], int n, int m)
{
int i;
srand(time(NULL));

for(i=0;i<n;i++)
{
a[i].no=i+1;
a[i].w=rand()%m+1;
a[i].p=rand()%n+1;
a[i].pw=(float)a[i].p/a[i].w;
}
}int planning(Good a[], int m,int n) //动态规划
{
int c[N+1][M+1];
int i,j;
for(i=0;i<=N;i++)
for(j=0;j<=M;j++)
c[i][j]=0;
for(i=1;i<=N;i++)
for(j=1;j<=M;j++)
if(a[i-1].w<=j)
if(a[i-1].p+c[i-1][j-a[i-1].w]>c[i-1][j])
c[i][j]=a[i-1].p+c[i-1][j-a[i-1].w];
else
c[i][j]=c[i-1][j];
else
c[i][j]=c[i-1][j];
for(i=N,j=M;i>=1;i--)//倒推求最优解
if(c[i][j]>c[i-1][j])
{
a[i-1].flag=1;
j=j-a[i-1].w;
}
return (c[n][m]);
}void main()
{
double Start,End;
Good a[N];
Start=clock();
initGoodSet(a,N,M);
printf("共获利%d\n",planning(a,M,N));
End=clock();
printf("所需时间为:%lf\n",(End-Start)/1000);
}