01背包问题-动态规划 整理成C语言！谢谢！

#include<stdio.h>

#include<stdlib.h>

int c[50][50]

int w[10],v[10]

int x[10]

int n

void KNAPSACK_DP(int n,int W)

void OUTPUT_SACK(int c[50][50],int k)

void KNAPSACK_DP(int n,int W)

{

int i,k

for(k=0k<=Wk++)

c[0][k]=0

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

{

c[i][0]=0

for(k=1k<=Wk++)

{

if(w[i]<=k)

{

if(v[i]+c[i-1][k-w[i]]>c[i-1][k])

c[i][k]=v[i]+c[i-1][k-w[i]]

else

c[i][k]=c[i-1][k]

}

else

c[i][k]=c[i-1][k]

}

}

}

void OUTPUT_SACK(int c[50][50],int k)

{

int i

for(i=ni>=2i--)

{

if(c[i][k]==c[i-1][k])

x[i]=0

else

{

x[i]=1

k=k-w[i]

}

}

x[1]=(c[1][k]?1:0)

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

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

}

void main()

{

int m

int i,j,k

printf("输入物品个数:")

scanf("%d",&n)

printf("依次输入物品的重量:\n")

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

scanf("%d",&w[i])

printf("依次输入物品的价值:\n")

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

scanf("%d",&v[i])

printf("输入背包最大容量:\n")

scanf("%d",&m)

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

printf("%4d",i)

printf("\n")

KNAPSACK_DP(n,m)

printf("构造最优解过程如下:\n")

for(j=1j<=5j++)

{

for(k=1k<=mk++)

printf("%4d",c[j][k])

printf("\n")

}

printf("最优解为:\n")

OUTPUT_SACK(c,m)

system("pause")

}

#include <stdio.h>

#include <string.h>

int f[1000+10],w[1000+10],v[1000+10]

int max(int x,int y)

{

if(x>y) return x

elsereturn y

}

int main()

{

int t,m,i,j

memset(f,0,sizeof(f))

scanf("%d %d",&t,&m)

for (i=1i<=mi++) scanf("%d %d",&w[i],&v[i])

for (i=1i<=mi++){

for (j=tj>=w[i]j--){

if(w[i]<=t)

f[j]=max(f[j-w[i]]+v[i],f[j])

}

}

printf("%d",f[t])

printf("\n")

}

01背包问题就是有个容量为W的包，然后有一堆的物品(1...n)，其中wi、vi分别为第i个物品的重量和价值，现在需要求的就是使得包中所装的物品尽可能的价值高。那么这个物品放不放在包中对应取值0

or

1。其算法为动态规划，需要证明最优子结构性质。用s[i][j]表示只有前i个物品且包容量为j时所能等到的最大价值，而有递归式

s[i][j]=

s[i-1][j],

wi>j

max{s[i-1][j],s[i-1][j-wi]+vi},

wi<=j

s[0][j]=0

1<=j<=W

s[i][0]=0

1<=i<=n

所以不论用什么语言实现，就是计算上面的式子，最终求得s[n][W]，上面的式子很好用递推实现的，这个是自底向上的，就是两层for；你也可以用栈实现自顶向下的，这个是记录式的方法。

以上的W是只考虑整数的。

---