C语言 典型背包问题 要源程序

//只是最基本的二维背包，比较好理解一点，可以有很多优化，一维也可以

#include<stdio.h>

#define N 1001

int V[N][N],w[N],v[N]

int max(int x,int y)

{return x>y?x:y}

int main()

{

int n,c,i,j

scanf("%d%d",&n,&c)//n表示物体个数，c表示容量

for (i=0i<=ni++) V[i][0]=0 //

for (j=0j<=cj++) V[0][j]=0 //

for (i=1i<=ni++) scanf("%d",&w[i])//重量

for (i=1i<=ni++) scanf("%d",&v[i])//价值

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

{

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

{

if (j<w[i])

V[i][j]=V[i-1][j]//(1)

else

V[i][j]=max(V[i-1][j], V[i-1][j-w[i]]+v[i]) //(2)

}

}

printf("%d\n",V[n][c])//返回背包取得的最大价值

return 0

}

(1)式表明：

如果第i个物品的重量大于背包的容量，则装入前i个物品得到的最大价值和装入前i-1个物品得到的最大价值是相同的，即物品i不能装入背包；

(2)式表明：

如果第i个物品的重量小于背包的容量，则会有以下两种情况：

（1）如果把第i个物品装入背包，则背包中物品的价值等于把前i-1个物品装入容量为j-wi的背包中的价值加上第i个物品的价值vi；

（2）如果第i个物品没有装入背包，则背包中物品的价值就等于把前i-1个物品装入容量为j的背包中所取得的价值。显然，取二者中价值较大者作为把前i个物品装入容量为j的背包中的最优解。

思路是：

1、先将所有东西按价值和重量的比值（价重比）从大到小排列。这里我用的冒泡排序。

2、将价重比大的先放到背包里。直到背包不能再放为止。此时价格就是最大的。

你应该能看懂。

#include <stdio.h>

#include <stdlib.h>

#include <time.h>

#define LIMIT 100

#define TN 20

typedef struct{

int weight//东西的重量

int value // 东西的价值

int selected // 是否放进去

}Things

void swap_things(Things *t1, Things *t2) // 只是一个交换函数而已。

{

int weight, value, selected

weight=t1->weight

value=t1->value

selected=t1->selected

t1->weight=t2->weight

t1->value=t2->value

t1->selected=t2->selected

t2->weight=weight

t2->value=value

t2->selected=selected

}

void sort_things(Things t[], int n) // 排序函数，按照价重比排序（价格与重量的比值）

{

int i,j

double vpw1=0, vpw2=0

for(i=0i<n-1i++)

{

for(j=n-1j>ij--)

{

vpw1=(double)t[j].value/t[j].weight //求出第 j 个东西的价重比

vpw2=(double)t[j-1].value/t[j-1].weight // 求出第j-1个东西的价重比

if(vpw1>vpw2) // 如果第 j 个的价重比大于 第 j-1个价重比，则将这两个东西的位置调换一下。

swap_things(&t[j],&t[j-1])

}

}

}

void select_things(Things t[], int n, int limit) // 这个函数用来选择要放进去的东西

{

int w=0, v=0,i

for(i=0i<ni++)

{

if(w+t[i].weight>limit) // 如果目前所有放进去的东西的重量大于限制的重量，就不放东西了

break

w+=t[i].weight // 计算目前所有放进去的东西的重量

v+=t[i].value// 计算目前所有放进去的东西的价格

t[i].selected=1 // 把这个东西标记为放进去了

}

printf("totel: weight=%d, value=%d\n",w,v) // 打印放进去的东西的总重量和总价格

}

int main(void)

{

Things t[TN]

int i

srand((unsigned)time(NULL))

for(i=0i<TNi++)// 初始化所有的东西的重量和价格

{

t[i].weight=rand()%TN+1

t[i].value=rand()%TN+1

t[i].selected=0

}

sort_things(t,TN)

select_things(t,TN,LIMIT)

printf("weight\tvalue\tselected\n")

for(i=0i<TNi++) // 打印所有东西的重量、价格和是否放进去。

printf("%d\t%d\t%d\n",t[i].weight,t[i].value,t[i].selected)

return 0

}

---