主题：第71次编程比赛题目
jowenshaw [专家分：0] 发布于 2008-08-22 19:46:00
0-1背包问题（整型）：
随机给定n（1<=n<=10000）个不大于100000正整数(a1,a2,...,an)和正整数v(1<=v<=999999999),请从n个给定的数中选出任意个数（每个数最多选取一次），使得这些数的总和不大于v，并且在不超过v的限制下其总和最大。如有多组最优解只需找出一组最优解就行。
程序先随机生成n个随机数和v的值，然后输出在给定数据下的一组最优解，无解时输出-1。请确保
程序在各种可能输入的情形下都有不错的效率，而不是只针对某些类型的数据，例如小数据类型，
小规模数据类型。
例如给定5个数据 2 2 4 6 10 和v值 15，则输出最优解为2 2 10 或 2 2 4 6 或 4 10 中的任意
一组。而 2 2 4 不是最优解，因为其总和小于可行解 2 2 10 的总和。 6 10 不是最优解，因为
其总和大于15.
评判标准： 正确性+时间效率+空间效率
比赛时间： 即日起至9月1日晚上11点整。
请在没有写出较高效率的解决方案之前轻视此题。再次强调一下程序的总体效率。如果实在不行请降低难度将n的取值范围限制为小于或等于100或更小，正确解决后再尝试改进。
回复列表 （共18个回复）
沙发
JackieRasy [专家分：3050] 发布于 2008-08-23 15:50:00
请问楼主，要在自己的程序中随机产生数据吗？
板凳
fenix124 [专家分：70] 发布于 2008-08-23 21:36:00
占楼先。
我的想法效率非常的低。但是也没有办法。就这样了
3 楼
JackieRasy [专家分：3050] 发布于 2008-08-24 16:29:00
#include<stdio.h>
#include<stdlib.h>
#include<time.h>
int cmp(const void*x,const*y)
{
return (*(int*)x-*(int*)y);
}
void BestSubArray(int num[],int v)
{
qsort((void*)num,n,sizeof(int),cmp);
int dis,sum=0;
int i,j=0,k;
for (i=n-1;i>=0;i--){
sum+=num[i];
dis=v-sum;
if(dis<0){
sum-=num[i];
continue;
}
else if (dis==0) { //本来想用栈进行操作，但是这里三种情况我一直没想好怎么统一
p[j++]=num[i];
break;
}
else p[j++]=num[i];
}
for(k=0;k<j;k++) printf("%d ",p[j]);
}
main()
{
int i=0,n,num[10000],p[10000];
srand(time(NULL));
n=rand()%10000+1;
for(i=0;i<n;i++){
num[i]=rand()%100000+1;
}
v=rand()%1000000000;
BestSubArray(int num[],int v);
}
4 楼
zd890907 [专家分：0] 发布于 2008-08-25 15:18:00
shi yixia
5 楼
姚姚的梦 [专家分：160] 发布于 2008-08-25 22:42:00
才有一点点感觉！
现在还解决不了!
6 楼
JackieRasy [专家分：3050] 发布于 2008-08-25 23:29:00
//对不起对不起！上面的代码有很低级的算法漏洞没有考虑到！请楼主测试本帖的代码，谢谢！
#include<stdio.h>
#include<stdlib.h>
#include<time.h>
#include<malloc.h>
int cmp(const void*x,const void*y)
{
return (*(int*)x-*(int*)y);
}
void BestSubArray(int num[n],int v)
{
int t,i,count;
for(t=n-1;t>=0;t--){
for (i=t;i>=0;i--){ //这个for循环求出排序后的num[t]中可能的最佳子数列
int sum=0,j=0,k;
sum+=num[i];
result[1].dis=v-sum;
if(result[1].dis<0){
sum-=num[i];
continue;
}
else if(result[1].dis==0){
result[1].p[j++]=num[i];
break;
}
else {result[1].p[j++]=num[i];}
}
if(result[1].dis<result[0].dis){ // 若本次遍历的值比上次更接近v
result[0].dis=result[1].dis;
count=j;
for(k=0;k<count;k++) {result[0].p[k]=result[1].dis[k];}
if(result[1].dis==0) break;
}
for(k=0;k<count;k++) printf("%d ",result[0].p[k]);
}
main()
{
typedef struct
{
int dis;//用来储存子数列之和与 v 的差
int *p;//用于储存子数列
}result[2];
p=(int*)malloc(10000*sizeof(int));
int i,n,num[10000],v;
srand(time(NULL));
n=rand()%10000+1;
for(i=0;i<n;i++){
num[i]=rand()%100000+1;
printf("%d ",num[i]);
}
v=rand()%1000000000;
struct result[0].dis=v;
qsort((void*)num,n,sizeof(int),cmp);
BestSubArray(int num[n],int v);
free(p);
}
7 楼
lpf46261479 [专家分：970] 发布于 2008-08-26 18:30:00
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>
#include <algorithm>
using namespace std;
#define N_NUM_MAX 10000
#define N_MAX 100000
#define V_MAX 999999999
int Number[N_NUM_MAX];
int Sum[N_NUM_MAX];
int n,v;
int main()
{
time_t Time;
int i,j,count=0;
srand((unsigned)time(&Time));
n=rand()%N_NUM_MAX+1;
v=rand()%V_MAX+1;
for(i=0;i<n;i++){
Number[i]=rand()%N_MAX+1;
}
sort(&Number[0],&Number[n-1]);
for(i=0;i<n&&count<=v;i++){
count+=Number[i];
}
if(count>v)
count--;
for(j=0;j<i;j++){
printf("%d ",Number[j]);
}
printf("%d",Number[j]);
return 0;
}
8 楼
ppc [专家分：3090] 发布于 2008-08-28 16:47:00
[code=c]
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
int e_v = 0;
int e_sum = -1;
int e_list = 0;
int getsum(int *a, int n){
int i = 0,
sum = 0;
for(i=0; i<=n; i++)
sum += a[i];
return sum;
}
int sorta(int *a, int ihead, int itail){
int i = ihead,
j = itail;
int curr;
int temp;
curr = i;
while(i < j){
if(curr == i){
if(a[curr] > a[j]){
temp = a[curr];
a[curr] = a[j];
a[j] = temp;
i++;
curr = j;
}
else
j--;
}
else if(curr == j){
if(a[curr] < a[i]){
temp = a[i];
a[i] = a[curr];
a[curr] = temp;
j--;
curr = i;
}
else
i++;
}
if(i == j){
sorta(a, ihead, i-1);
sorta(a, i+1, itail);
break;
}
}
return 0;
}
int next_pre_match(int *a, int *status, int count){
int i = 0,
j = 0,
flag = 0;//0:used, 1:noused, 2:used count
int first_noused_sum = 0,
second_used_count = 0;
Next1:
while(i<count){
if(flag == 0){
if(status[i] != 0)
i++;
else
flag = 1;
}
else if(flag == 1){
if(status[i] ==0){
first_noused_sum += a[i];
i++;
}
else
flag = 2;
}
else if(flag == 2){
second_used_count = a[i];
break;
}
}
if(flag !=2)
return 100;
if(first_noused_sum <= second_used_count){
flag = 0;
i++;
goto Next1;
}
else{
status[i-1] = status[i] - a[i] + a[i-1];
status[i] = 0;
for(j=0; j<i-1; j++)
status[j] = 0;
}
return 0;
}
int copy_point(int *a, int *b, int *status, int count){
int i = 0, j = 0;
for(i=0; i<count; i++)
if(status[i] != 0)
b[j++] = a[i];
b[j] = -1;
return j;
}
int fun(int *a, int *b, int *c, int count){
int i = count,
all_temp = 0,
sum_temp = 0,
sum = 0,
j = 0,
tail = 0,
rc = 0;
int *status = (int*)malloc(sizeof(int)*count);
for(j=0; j<count; j++)
status[j] = 0;
LOOP1:
for(j=0; j<count; j++){
if(status[j] != 0){
sum = status[j];
i = j;
break;
}
}
tail = copy_point(a, b, status, count);
LOOP2:
all_temp = getsum(a, i-1);
if(all_temp + sum <= e_sum){
for(j=0; j<i; j++)
status[j] = 1;
rc = next_pre_match(a, status, count);
if(rc == 100)
return 1;
goto LOOP1;
}
sum += a[i-1];
if(sum > e_v){
sum -= a[i-1];
i--;
if(i==0){
if(e_sum < sum){
e_sum = sum;
j = 0;
while(b[j] >= 0){
c[j] = b[j];
j++;
}
c[j] = -1;
}
rc = next_pre_match(a, status, count);
if(rc == 100)
return 1;
goto LOOP1;
}
goto LOOP2;
}
else if(sum == e_v){
b[tail] = a[i-1];
b[tail+1] = -1;
e_sum = sum;
return 10;//equl
}
else{
b[tail] = a[i-1];
tail++;
b[tail] = -1;
status[i-1] = sum;
i--;
if(i==0){
if(e_sum < sum){
e_sum = sum;
j = 0;
while(b[j] >= 0){
c[j] = b[j];
j++;
}
c[j] = -1;
}
rc = next_pre_match(a, status, count);
if(rc == 100)
return 1;
goto LOOP1;
}
else
goto LOOP2;
}
return 0;
}
[/code]
9 楼
ppc [专家分：3090] 发布于 2008-08-28 16:50:00
[code=c]
int main(){
int v = 5, j = 0, n = 0, rc = 0;
int *a;
int *b;
int *c;
/* b and c are just used for store the choosed counts */
int all_sum = 0;
printf("Input the number of counts:");
scanf("%d", &n);
a = (int *)malloc(sizeof(int) * n);
b = (int *)malloc(sizeof(int) * n);
c = (int *)malloc(sizeof(int) * n);
printf("Input the counts:\n");
srand((int)time(0));
for(j=0; j<n; j++){
scanf("%d", &a[j]);
/*
a[j] = 1+(int)(10000.0*rand()/(RAND_MAX+1.0));
*/
b[j] = -1;
c[j] = -1;
/*
printf("%5d ", a[j]);
if((j+1)%10==0)
printf("\n");
*/
}
printf("Input the special count(v):");
scanf("%d", &v);
/*
v = 1+(int)(999999999.0*rand()/(RAND_MAX+1.0));
printf("v=%d\n", v);
*/
all_sum = getsum(a, n-1);
if(all_sum <= v){
for(j=0; j<n; j++)
printf("%d+", a[j]);
printf("\b");
printf("=%d\n", all_sum);
return 0;
}
e_v = v;
sorta(a, 0, n-1);
j = 0;
rc = fun(a, b, c, n);
if(e_sum == -1){
printf("-1\n");
return 0;
}
if(rc == 10){
while(b[j] >= 0){
printf("%d+", b[j]);
j++;
}
}
else{
while(c[j] >= 0){
printf("%d+", c[j]);
j++;
}
}
printf("\b");
printf("=%d\n", e_sum);
return 0;
}
[/code]
10 楼
mark0626 [专家分：50] 发布于 2008-08-28 21:37:00
有谁有结果了?
我来回复
您所在位置：