C语言动态规划——0-1背包问题

Python014

C语言动态规划——0-1背包问题,第1张

以前写的 自己看吧

#include<stdio.h>

int w[5]={0,3,5,2,1},p[5]={0,9,10,7,4}

int c=7,n=4

int cw=0,cp=0,bestp=0

int x[10]={0}

void try(int k)

{

int i

if(k>n)

{

for(i=1i<=ni++)

printf("%2d",x[i])

printf("%d %d\n",cw,cp)

if(bestp<cp)

bestp=cp

}

else

{

x[k]=1

cw=cw+w[k]

cp=cp+p[k]

if(cw<=c)

try(k+1)

x[k]=0

cw=cw-w[k]

cp=cp-p[k]

if(cw<=c)

try(k+1)

}

}

main()

{

clrscr()

try(1)

printf("best_P=%d",bestp)

}

•程序要求

•动态规划的过程必须通过DProcessing( wi , vi , m[i,j] ) 计算

•wi表示物品 i的重量，

•vi 代表物品 i的价值，

•m[ i,j ] 代表当前正在规划的重量为 j 的背包 的价值

•注：动态规划的过程禁止直接写在主函数中！