背包问题相信学过算法的都不陌生，有很多种背包的模型，今天我们的背包问题是这样的：
小A有一个背包，他要背着它去野营，背包的容积是V，也就是说背包最多能装总体积为V的物品，假设现在已经有K种物品小A能够装进背包，每种物品都有它的体积，求出小A的背包能够装的物品的最大总体积为多少
输入
第一行:
背包体积V 和物品数量K
接下来K行：
每个物品对应的体积v

每个输入均为整数(其中V<=1000,K<=50)

竞赛事项： http://www.bc-cn.net/bbs/dispbbs.asp?boardID=5&ID=31744&page=1

[此贴子已经被作者于2005-11-1 16:30:33编辑过]

我觉得吧，搂主要把题目描述的更详细一点。

这道题就不如上一道题，如n!清楚。
我没看过很深奥的算法，是不是就不能参加这题目了呢？

背包的容积是V，也就是说背包最多能装总体积为V的物品
求出小A的背包能够装的物品的最大总体积为多少

欢迎参加，我特别欢迎C++Coder参加，尤其是kai

--------------
100 11
15
52
4
23
8
21
3
6
7
34
99
------------------
请问上面算不算一个正确的输入文件,V=100,现在有11件物品,算一下最多能装几件,最大容积是多少?
那物品数优先还是容积优先?
另:统一下输入文件的名称和V及物品数吧,这们测试的时候方便一些.

是体积优先，
给个例子，比如输入是
10 4
8
1
3
5
那么输出应该是
9
可能方案有2个，8+1和1+3+5
比如8+3就不是个合法的方案，因为它超过了背包的最大容积10（8+3=11）

好难，不会，呵呵。

我是刚学C不久,以前用VB,至于C只会简单的程序实现,还不懂得怎样提高程序的通用性,在效率上也差很多.比如N!那题,我是在C++板块见到的,也写了一个,可是没人理会,几位板主的代码我根本看不懂.

这个程序我完成了,只是简单的算出了结果,至于其它的我就不会了,包括验证我只会用计算器一下一下的按.

代码如下,在WIN-TC下写的:

/*////////////////////////////////////////////////////////////*/
#include<stdio.h>
#include<string.h>
int main()
{
int v,k,array[1000];
int i,j,max,sum=0,reslen=0,res[500];
FILE *fp;char filename[20];
clrscr();
printf("\nInput filename:");
scanf("%s",filename);
if((fp=fopen(filename,"r"))==NULL)
{
printf("\nCannot open file.\n");
exit(1);
}
/*读入数据*/
fscanf(fp,"%d%d",&v,&k);
for(i=0;i<k;++i)
fscanf(fp,"%d",&array[i]);
fclose(fp);
/*输出读入的数据*/
printf("v=%d\tk=%d\n\nSorted:",v,k);
/*对K个物品进行排序(选择法)并输出*/
for(i=0;i<k-1;++i)
{
max=i;
for(j=i+1;j<k;++j)
if(array[max]<array[j])max=j;
if(max!=i)
{
array[max]+=array[i];
array[i]=array[max]-array[i];
array[max]=array[max]-array[i];
}
}
for(i=0;i<k;++i)
printf("%6d",array[i]);
printf("\n");

/*算法核心代码*/
for(i=0;i<k-1;++i)
{
if(array[i]>v)
continue;
else
sum=array[i];
for(j=i+1;j<k;++j)
{
sum+=array[j];
if(sum>v)
{
sum-=array[j];
continue;
}
}
res[reslen]=sum;
++reslen;
/*sum=0;*/
}
for(i=0;i<reslen;++i)
j=j<res[i]?res[i]:j;
printf("\nThe max is:%d",j);
getch();
}
/*////////////////////////////////////////////////////////*/

我用的方法是先将K个物品按体积降序排列,从第一数开始与后面的数相加,超过V就加下一个数,循环一次后将结果存入数组,再从第二个数开始试,直到循环结束.最后从数组中选择最大的数输出.

错了别笑我,我可以改的...

[此贴子已经被作者于2005-11-3 20:10:24编辑过]

最大努力了,再不行我就只等看别人的了:
#include<stdio.h>
#include<string.h>
#include<stdlib.h>
int main()
{
int v,k,array[1000];
int i,j,l,max,sum,result=0;
FILE *fp;char filename[20];
clrscr();
printf("Input filename:");
scanf("%s",filename);
if((fp=fopen(filename,"r"))==NULL)
{
printf("\nCannot open file.\n");
exit(1);
}
/*读入数据*/
fscanf(fp,"%d%d",&v,&k);
for(i=0;i<k;++i)
fscanf(fp,"%d",&array[i]);
fclose(fp);
/*输出读入的数据*/
printf("v=%d\tk=%d\n\nSorted:",v,k);
/*对K个物品进行排序(选择法)并输出*/
for(i=0;i<k-1;++i)
{
max=i;
for(j=i+1;j<k;++j)
if(array[max]<array[j])max=j;
if(max!=i)
{
array[max]+=array[i];
array[i]=array[max]-array[i];
array[max]=array[max]-array[i];
}
}
for(i=0;i<k;++i)
printf("%6d",array[i]);
printf("\n");

/*算法核心代码*/
for(i=0;i<k-1;++i)
{
if(array[i]>v)
continue;
else
sum=array[i];
for(l=1;l<k-i-2;++l)
{
printf("%d",array[i]);
for(j=i+l;j<k;++j)
{
sum+=array[j];printf("+%d",array[j]);
if(sum>v)
{
sum-=array[j];printf("-%d",array[j]);
}
}
printf("=%d\n",sum);
result=sum>result?sum:result;
sum=array[i];
}
}
printf("\nThe max is:%d",result);
}
以下是输入:
100 12
13
60
3
44
70
90
27
9
35
7
80
18
以下是输出:
v=100 k=12

Sorted: 90 80 70 60 44 35 27 18 13 9 7 3
90+80-80+70-70+60-60+44-44+35-35+27-27+18-18+13-13+9+7-7+3-3=99
90+70-70+60-60+44-44+35-35+27-27+18-18+13-13+9+7-7+3-3=99
90+60-60+44-44+35-35+27-27+18-18+13-13+9+7-7+3-3=99
90+44-44+35-35+27-27+18-18+13-13+9+7-7+3-3=99
90+35-35+27-27+18-18+13-13+9+7-7+3-3=99
90+27-27+18-18+13-13+9+7-7+3-3=99
90+18-18+13-13+9+7-7+3-3=99
90+13-13+9+7-7+3-3=99
90+9+7-7+3-3=99
80+70-70+60-60+44-44+35-35+27-27+18+13-13+9-9+7-7+3-3=98
80+60-60+44-44+35-35+27-27+18+13-13+9-9+7-7+3-3=98
80+44-44+35-35+27-27+18+13-13+9-9+7-7+3-3=98
80+35-35+27-27+18+13-13+9-9+7-7+3-3=98
80+27-27+18+13-13+9-9+7-7+3-3=98
80+18+13-13+9-9+7-7+3-3=98
80+13+9-9+7+3-3=100
80+9+7+3=99
70+60-60+44-44+35-35+27+18-18+13-13+9-9+7-7+3=100
70+44-44+35-35+27+18-18+13-13+9-9+7-7+3=100
70+35-35+27+18-18+13-13+9-9+7-7+3=100
70+27+18-18+13-13+9-9+7-7+3=100
70+18+13-13+9+7-7+3=100
70+13+9+7+3-3=99
70+9+7+3=89
60+44-44+35+27-27+18-18+13-13+9-9+7-7+3=98
60+35+27-27+18-18+13-13+9-9+7-7+3=98
60+27+18-18+13+9-9+7-7+3-3=100
60+18+13+9+7-7+3-3=100
60+13+9+7+3=92
60+9+7+3=79
44+35+27-27+18+13-13+9-9+7-7+3=100
44+27+18+13-13+9+7-7+3-3=98
44+18+13+9+7+3=94
44+13+9+7+3=76
44+9+7+3=63
35+27+18+13+9-9+7+3-3=100
35+18+13+9+7+3=85
35+13+9+7+3=67
35+9+7+3=54
27+18+13+9+7+3=77
27+13+9+7+3=59
27+9+7+3=46
18+13+9+7+3=50
18+9+7+3=37
13+9+7+3=32

The max is:100

[此贴子已经被作者于2005-11-4 20:49:13编辑过]

我也发现了,在遇到下面这组数时得不到正确结果:
100 6
90
8
5
4
3
3
1
只是我找不到更好的方法了.上面这组数存在"中间跳跃"的问题,改进后能得到正确结果,但修改一下输入仍存在问题,还有"下跳跃"和"多级跳跃"问题存在.

用递归的方法会好些,但我不会呀.

"跳跃"的意思也就是说在我的算法中,当加第N个数没有大于V时只能向下继续加,没有忽略N而从N+1开始(或再向下"跳跃"的问题)的选择,上面的输入就是针对我的算法选的,输出为99,而90+4+3+3或90+5+4+1都是最大值......

我的代码再改进也做不到K=50的"多级跳跃"!!我还是再想想吧.....

核心算法描述:用的还是穷举的办法,中间加入了一个循环(这样虽多了N次计算,但加入了"跳跃"的方法),并列出最大值的数据相加过程. 再精简的话就是我现在做不到的了......