来迟了我晕 能不能给个期限呀 以后这些竞赛~~~

#include<stdio.h>
#include<math.h>

void main()
{
int w,k,sum,max=0;
int a[100],sign[100];
long i,j,l;
scanf("%d,%d",&w,&k);
for(i=0;i<k;i++)
scanf("%d",&a[i]);

for(i=0;i<pow(2,k);i++)
{
l=0;
j=i;
while(j>0)
{
sign[l++]=j%2;
j/=2;
}
sum=0;
for(j=0;j<k;j++)
if(sign[j]==1)
sum+=a[j];
if(sum<=w&&sum>max)
max=sum;
}
printf("Max=%d",max);
getch();
}

不好意思,刚刚看到这个帖子.

我正在看背包问题的算法, 突然想看看我们的论坛上是不是有这样类似的帖子, 搜索之后就看到了这个帖子.

背包问题是这样的:

你有一个包，包的体积上限为V, 最初包是空的。
你有n 件东西，每件东西都具有体积和价值两个数据。
比如第一件物体的体积为v1， 价值为 c1
第二件物体的体积为v2， 价值为 c2
第三件物体的体积为v3， 价值为 c3
。
。
。
第 n-1 件物体的体积为v n-1， 价值为 c n-1 // 此处 n-1 为 Index 值
第 n 件物体的体积为v n， 价值为 c n // 同样，此处 n 为 Index 值

你的任务是往包里放东西，使得包里的物件的总价值最高。

我在网上看了很多相关的算法，以及源代码。
下面给大家一个通过google 搜索的连接网页，大家可以自己点击去看看：
http://www.google.de/search?q=%E8%83%8C%E5%8C%85%E9%97%AE%E9%A2%98&btnG=Suche&hl=de&as_qdr=all

我在看了很多关于此题的相关算法之后，突然在想，是不是他们的算法太繁琐了，还是我的想法不对？
下面我将我的算法描述如下：
由于我知道 n 件物件的体积和价值，那么我就可以知道每件物件的价值比： Ci / Vi 此处i 为index
然后我根据物件的价值比排序（降序排序）
现在我从序列中取出第一件物体（该物体的价值比为最高的），我问我自己一个问题，是不是该物体能放进包中，也就是包的当前体积应该大于该物件的体积。如果可以放进去，那么将该物件放进包中，此时包的体积为包的原体积减去该物件的体积，也就是说我们必须对包的体积update. 如果放不进去，那么我们就继续从序列中取下一个物件，同样的，我们必须判断，该物件是不是可以放进包中，如果可以放进去，那就放进去，然后update 包的体积。然后继续试着放东西，直到对所有在序列中的物件都尝试过。

观察上面的算法，可以看出，算法的时间开销取决于排序而非取决于放东西，因为放东西是一个遍历的过程，也就是说放东西的时间开销为 O(n)， 那么最高效的排序是什么呢？ 答案是 QuickSort， QuickSort 的时间开销为 O(nlog(n)) 所以如果我的算法正确的话，那么该算法的时间开销即为 O(nlog(n))

大家看看，是不是有什么想法？如果有，说来听听。

如果以最大价值优先那 kai 的想法无疑是正确的

而事实上并不一定是最大值优先的
如：Ｖ＝９
４个物品体积：８　５　４　２
然而，您得选５　４
而不是８

我只能用穷举了……
定义个数组０，１辅助串，长度为n，从00……1到11……1变化
为１则对应物品体积选中，找出体积小于v且最接近的组合即可。
跟那个石头归差不多，

soft_wind，
我看了你的例子,虽然不完整,但我感觉到了什么. 我的算法的确有问题. 但我的直觉告诉我,价值比是一个比较有意思的因素. 算法需要做一定的修正.

依你的例子，做一个说明:
4个物品：a(80, 8), b(80, 5), c(80, 4) d(80, 4) // 这里括号中的第一个数据为价值
// 第二个数据为体积
这样可以得出，他们的价值比为
a的价值比就是 80/8 = 10
b的价值比就是 80/5 = 16
c的价值比就是 80/4 = 20
d的价值比就是 80/2 = 40

这样的话，根据价值比降序排列以后就是如下的次序:
d, c, b, a

现在先取d, 包的剩下体积为 9-2 = 7
然后取c, 包的剩下体积为 7-4 = 3
随后就不能再取了。 这样包内总价值为 160

如果我们取c, b 放入包内，我们同样得到总价值 160

这个时候，如果我修改一个数据，问题就出来了，我将b的价值修改为81，他们的价值比的次序没有变，但是这时如果把b, c 放入包内，那么总价值为 161
把d, c 放入包内，总价值为 160， 所以我的算法有问题。

呵呵，其实刚才我并没仔细看您上面的帖子，
原来您是在讲原来的背包问题．．．．
我只是对版主老大的话提一下意见而已。

#include "stdio.h"
#include "conio.h"
#include "math.h"
main()
{
int totalv;
int num,sum=0,i,j,k,p,suffix=0,time,result,flag=1;
int *depart=NULL,*store=NULL;
short *help=NULL;
printf("Please input the total bulk:");
scanf("%d",&totalv);
printf("Please input the number of all the things:");
scanf("%d",&num);
depart=(int *)malloc(sizeof(int)*num);
store=(int *)malloc(sizeof(int)*num);
help=(short *)malloc(sizeof(short)*num);
for(i=0;i<num;i++)
scanf("%d",&depart[i]);
for(i=0;i<num;i++)
help[i]=1;
time=pow(2,num);
for(p=0;p<time;p++)
{
for(k=0;k<num;k++)
if(help[k]==1)
sum+=depart[k];
if(sum<=totalv)
{

if(flag)
{
flag=0;
result=sum;
for(k=0;k<num;k++)
if(help[k]==1)
store[suffix++]=depart[k];
}
else
{
suffix=0;
if(sum>result)
{
for(k=0;k<num;k++)
store[k]=0;
result=sum;
for(k=0;k<num;k++)
if(help[k]==1)
store[suffix++]=depart[k];
}
}
}
for(j=i-1;j>-1;j--)
if(help[j]==1)
{
help[j]=0;
for(k=j+1;k<num;k++)
help[k]=1-help[k];
break;
}
sum=0;
}
printf("%d\n",result);
for(k=0;store[k];k++)
printf("%4d",store[k]);

free(help);
free(store);
free(depart);
getch();
}


把石头归并的那个程序稍微改了下，就是这个了