第71次编程比赛题目 — 编程爱好者社区

主题：第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或更小，正确解决后再尝试改进。

本帖地址： http://bbs.pfan.cn/post/283251.html

回复列表（共18个回复）

11 楼

qiuxumin1 [专家分：0] 发布于 2008-08-29 10:43:00

12 楼

fandy [专家分：0] 发布于 2008-08-29 19:24:00

好的

13 楼

Cer_Rex [专家分：0] 发布于 2008-08-29 20:26:00

新手，小试一下下。
#include <stdio.h>
#include <time.h>
#include <stdlib.h>

int  n;   /*1<=n<=10000*/
long v;   /*1<=v<=999 999 999*/
long  *head; /*储存n个随机数*/
/*初始化各变量*/
void getrand(void)
   {
   int i;
   randomize();
   n=random(10001)+1;
   v=random(31623);
   v=v*random(31623)+random(32767)+random(16349)+1;
   /*v=random(10000)*100000+random(32767)*3+random(1702)+1;*/
   head=(long *)malloc(n*sizeof(long));
   for(i=0;i<n;i++)
     head[i]=random(100001);
   }
/*排序*/
void sorters(void)
{
int i,j,exch;
for(i=0;i<n;i++)
  for(j=0;j<n-1-i;j++)
    if(head[j]<head[j+1])
      {
      exch=head[j];
      head[j]=head[j+1];
      head[j+1]=exch;
      }
}
/*找出题解*/
int solutions(void)
{
int  min=head[n-1];
int  i;
long nv=0;
if(min>v)
  return -1;
for(i=0;i<n;i++)
  {
  if(nv+head[i]>v)
    {
    head[i]=-1;
    continue;
    }
  nv+=head[i];
  }
return 1;
}
/*打印出解*/
void results(void)
{
int i;
printf("\nResult:\n");
for(i=0;i<n;i++)
  if(head[i]!=-1)
    printf("%d ",head[i]);
}

main()
{
getrand();
sorters();
if(solutions()!=-1)
  results();
else
  printf("\nNo answers!");
}

14 楼

szjrabbit [专家分：0] 发布于 2008-08-30 14:03:00

#include <stdio.h>
#include <stdlib.h>
#include <time.h>

#define V_MAX 999999999
#define N_MAX 100000

void sort(long int a[],int n);

int main(void)
{
         int i;
         srand((unsigned)time(NULL));
         int n=random()%10000;

         long int v=random()%V_MAX;

    printf("the value of v is %d\n",v);
    long int *p_int=(long int *)malloc(sizeof(long int)*n);

    //初始化给定的数组,如果随机产生的数大于v,则在数组中该项值为1.
    for (i=0;i<n;i++){
        *(p_int+i)=random()%N_MAX;
        if (*(p_int+i) > v)
            *(p_int+i) = -1;
    }
    sort(p_int,n);//对数组按从大到小进行排序

    //遍历数组,找出符合条件的值
    for (i=0; i<n && *(p_int+i) != -1;i++){
        if (v > p_int[i]){
            v-=p_int[i];
            printf(" %d,",p_int[i]);
        }
    }
    printf("\n");
    if (i == 0)
        return -1;
    return 0;
}

void sort(long int a[],int n)
{
    int i,j,max,temp;
    for (i=0;i<n-1;i++){
        max=a[i];
        temp=i;
        for (j=i+1;j<n;j++){
            if (a[j]>max){
                max=a[j];
                temp=j;
            }
        }
        a[temp]=a[i];
        a[i]=max;

    }

}

15 楼

apart789 [专家分：640] 发布于 2008-08-31 13:21:00

/*当前的VC里rand()产生的数在0-32767之间，所以产生不了题目中要求的那么大的随机数，因此我写了两个版本
一个就是直接用rand()产生随机数，不过都是小的数，另一个就是稍作修改，产生的一般都是大数*/
#include<iostream>
#include<vector>
#include<stack>
#include<algorithm>
#include<time.h>
using namespace std;
#define MAX 10000
#define MAX1 100000
#define MAX2 999999999
int main()
{
    int n,a,i,j,k,flag=0;
    long v,sum=0,s,resultsum=0;
    vector<int> ivec;
    stack<int> result,sta;
    cout<<"程序随机生成的数字个数n(1<=n<=10000):"<<endl;
    srand( (unsigned)time(NULL));
    n=rand()%MAX+1;
    cout<<n<<endl;
    cout<<"随机产生n个数字(1=<a<=100000)如下"<<endl;
    for(i=0;i<n;i++)
    {
       a=rand()%MAX1+1;
       ivec.push_back(a);
       cout<<a<<"\t";
    }
    cout<<endl;
    sort(ivec.begin(),ivec.end());
    v=rand()%MAX2+1;
     cout<<"随机生成的正整数v(1<=v<=999999999): "<<v<<endl;
    k=n-1;
    do
    {
        for(j=k;j>=0;j--)
        {
            s=sum+(ivec[j]);
            if(s==v)
            {
                flag=1;
                resultsum=s;
                result=sta;
                result.push(j);
                break;
            }
            else
                if(s<v)
                {
                    sta.push(j);
                    sum=s;
                }

            if(sum>resultsum)
               {
                resultsum=sum;
                result=sta;
               }
        }
        if(flag==1) break;
        if(!sta.empty())             //以2 3 4 6 10，v=15为例,sta栈中先把4退出栈,
        {                            //而后把此时的k设为4后面的一个元素3,然后再回到for循环,那刚好3和2进栈后就为15了.
           i=sta.top();                 //但若此时还不能确定最优解,看例子2 2 4 6 10（此时为10和4）,4退栈,2 2进栈,sum=14,
           k=i-1;                     //不能确定最优解，这时可以确定以10开头的最优解都已完毕，因为和前一次的最优解没差别
           sta.pop();                 //所以还是取前一次的数（因为result栈还没起变化）
           sum-=ivec[i];
           if(k==-1)
           {
               while(!sta.empty())
               {
                   j=sta.top();
                   sum-=ivec[j];
                   sta.pop();
                   if(j!=++i)
                    {
                         k=j-1;
                         break;
                     }
               }
           }
        }
    }while(k!=-1);
    if(resultsum==0)
    {
        cout<<"-1"<<endl;

    }
    else
    {
        cout<<"最优解:"<<resultsum<<endl;
        while(!result.empty())
        {
            a=result.top();
            result.pop();
            cout<<ivec[a]<<" ";
        }
    }
   return 0;
}

16 楼

umi1st [专家分：0] 发布于 2008-08-31 14:26:00

看一下

17 楼

apart789 [专家分：640] 发布于 2008-08-31 16:12:00

//此版本产生的一般都是很大的数
#include<iostream>
#include<vector>
#include<stack>
#include<algorithm>
#include<time.h>
using namespace std;
int main()
{
    int n,a,b,c,data,i,j,k,flag=0;
    int v,sum=0,s,resultsum=0;
    vector<int> ivec;
    stack<int> result,sta;
    cout<<"程序随机生成的数字个数n(1<=n<=10000):"<<endl;
    srand((unsigned)time(NULL));
    n=rand()%10000+1;
    cout<<n<<endl;
    cout<<"随机产生n个数字(1=<data<=100000)如下"<<endl;
    for(i=0;i<n;i++)
    {
       a=rand()%10000;
       b=rand()%10;
       data=a*10+b+1;
       ivec.push_back(data);
       cout<<data<<"\t";
    }
    cout<<endl;
    sort(ivec.begin(),ivec.end());
    a=rand()%1000;
    b=rand()%1000;
    c=rand()%1000;
    v=a*1000000+b*1000+c+1;
     cout<<"随机生成的正整数v(1<=v<=999999999): "<<v<<endl;
    k=n-1;
    do
    {
        for(j=k;j>=0;j--)
        {
            s=sum+(ivec[j]);
            if(s==v)
            {
                flag=1;
                resultsum=s;
                result=sta;
                result.push(j);
                break;
            }
            else
                if(s<v)
                {
                    sta.push(j);
                    sum=s;
                }

            if(sum>resultsum)
               {
                resultsum=sum;
                result=sta;
               }
        }
        if(flag==1) break;
        if(!sta.empty())             //以3 4 6 10，v=15为例,sta栈中先把退出栈,
        {                            //而后把此时的k设为后面的一个元素,然后再回到for循环,那刚好和进栈后就为了.
           i=sta.top();                 //但若此时还不能确定最优解,看例子2 4 6 10（此时为和）,4退栈,2 2进栈,sum=14,
           k=i-1;                     //不能确定最优解，这时可以确定以开头的最优解都已完毕，因为和前一次的最优解没差别
           sta.pop();                 //所以还是取前一次的数（因为result栈还没起变化）
           sum-=ivec[i];
           if(k==-1)
           {
               while(!sta.empty())
               {
                   j=sta.top();
                   sum-=ivec[j];
                   sta.pop();
                   if(j!=++i) {k=j-1;break;}
               }
           }
        }
    }while(k!=-1);
    if(resultsum==0)
    {
        cout<<"-1"<<endl;

    }
    else
    {
        cout<<"最优解:"<<resultsum<<endl;
        while(!result.empty())
        {
            a=result.top();
            result.pop();
            cout<<ivec[a]<<" ";
        }
    }
   return 0;
}

18 楼

ckeryradish [专家分：140] 发布于 2008-08-31 21:59:00

模仿书的例子，n*v的复杂性，无法满足题目的要求。凑下热闹.......

#define PRINT(info) {std::cout << info << std::endl;}
#define PRINT_VAL(val) {std::cout << #val" = " << val << std::endl;}

int DP_int_knapsack(int w[], int n, int v)
{
    //w[i]不大于100000正整数(a1,a2,...,an)
    //1<=n<=10000
    //1<=v<=999999999
    int i = 0;
    int j = 0;

    //程序无解的唯一情况是
    //每个数w[i]都比v大
    int iMinW = w[0];
    for (i = 1; i <n; i++)
    {
        if (w[i] < iMinW)
        {
            iMinW = w[i];
        }
    }
    if (iMinW > v)
    {
        PRINT("NO answer!");
        return -1;
    }
    else
        if (iMinW == v)
        {
            PRINT("best answer: " << v);
            PRINT_VAL(v);
            return v;
        }

    int *pV = new(std::nothrow) int[(n + 1) * (v + 1)];
    if (NULL == pV)
    {
        PRINT("need too much memory!");
        return -1;
    }
    //初始化第一行, 选择个数为0时，结果为0
    for (j = 0; j <= v; j++)
    {
        pV[0 * (v + 1) + j] = 0;
    }

    //初始化第一排, 数为0时，结果为0
    for (i = 0; i <= n; i++)
    {
        pV[i * (v + 1) + 0] = 0;
    }

    for (j = 1; j <= v; j++)
    for (i = 1; i <= n; i++)
    {
        //假定第i 个数不选
        int iTmpMax = pV[(i - 1) * (v + 1) + j];
        pV[i * (v + 1) + j] = iTmpMax;

        //现在判断是否可以选第i个数
        if (j - w[i - 1] >= 0)
        {
            int iTmp = pV[(i - 1) * (v + 1) + j - w[i - 1]] + w[i - 1];
            if (iTmp <= v && iTmp > iTmpMax)
            {
                pV[i * (v + 1) + j] = iTmp;
            }
        }
    }

    int iMaxV = pV[n * (v + 1) + v];

    PRINT("best answer: " << iMaxV);

    //反向递推出那些数据被选中
    j = iMaxV;
     for (i = n; i > 0; i--)
    {
        if (pV[i * (v + 1) + j] > pV[(i - 1) * (v + 1) + j])
        {
            PRINT("w[" << i - 1 << "] = " << w[i - 1]);
            j -= w[i - 1];
        }
    }

    delete []pV;
    return iMaxV;
}

我来回复

您尚未登录，请登录后再回复。点此登录或注册

主题：第71次编程比赛题目

回复列表（共18个回复）

我来回复

程序员工具箱 new

代码片段

本版新帖

主题：第71次编程比赛题目

回复列表 （共18个回复）

我来回复

程序员工具箱 new

代码片段

本版新帖

回复列表（共18个回复）