首页 > ACM题库 > HDU-杭电 > hdu 2592 Candidate superkey-背包问题-[解题报告]C++
2014
02-10

hdu 2592 Candidate superkey-背包问题-[解题报告]C++

Candidate superkey

问题描述 :

A database table consists of a set of columns called attributes, and a set of rows called entries. A superkey is a set of attributes such that each entry’s values for those attributes forms a unique ordered set. That is, for any superkey, each pair of entries differs in at least one of the attributes contained within the superkey. A candidate superkey is a superkey such that no proper subset of its attributes forms a superkey. (A proper subset of a superkey is a set of attributes that is formed by removing one or more attributes from the superkey.)

输入:

The input file contains several test cases. Each test case begins with two integers n and m ( 2<=n<=30, 1<=m<=10 ), which indicate the size of the table. Then n lines follow, each line contains m uppercase letters (‘A’-'Z’) to represent one entry.

输出:

The input file contains several test cases. Each test case begins with two integers n and m ( 2<=n<=30, 1<=m<=10 ), which indicate the size of the table. Then n lines follow, each line contains m uppercase letters (‘A’-'Z’) to represent one entry.

样例输入:

2 3
ABC
ABC
2 1
A
B
3 3
ABC
ACD
BBE

样例输出:

0
1
2

     这题实际上是一个01背包问题。开始的时候把被抓的概率作为花费乘以100、1000甚至1000000来运算,结果不是wa就是tle。。。。

      后来上网看了题解,发现这是很巧妙的01背包问题。解决问题的时候是要把不被抓到的概率作为价值,而抢到的钱作为花费,求出在安全概率最高的情况下所抢到的钱。

 

以下是实现代码:

    

     

#include<cstdio>
#include<iostream>
using namespace std;
const int N=110;
const int M=100001;
double safety[N],bag[M];
int money[N];
int sum,n;

void beibao()
{
 int i,j;
 for(i=0;i<=sum;i++)
  bag[i]=0.0;
 bag[0]=1.0;
 for(i=1;i<=n;i++)
  for(j=sum;j>=money[i];j--)
  {
   bag[j]=bag[j]>(bag[j-money[i]]*safety[i])?bag[j]:(bag[j-money[i]]*safety[i]);
  }
}

int main()
{
 int t;
 scanf("%d",&t);
 while(t--)
 {
  double p;
  scanf("%lf%d",&p,&n);
  int i,j;
  sum=0;
  for(i=1;i<=n;i++)
  {
   scanf("%d%lf",&money[i],&safety[i]);
   safety[i]=1.0-safety[i];
   sum+=money[i];
  }
  beibao();
  p=1.0-p;
  for(i=sum;bag[i]<p;i--);
  printf("%d/n",i);
 }
 return 0;
}

 

解题转自:http://blog.csdn.net/new_c_yuer/article/details/6314477


  1. 第二个方法挺不错。NewHead代表新的头节点,通过递归找到最后一个节点之后,就把这个节点赋给NewHead,然后一直返回返回,中途这个值是没有变化的,一边返回一边把相应的指针方向颠倒,最后结束时返回新的头节点到主函数。

  2. #include <stdio.h>
    int main(void)
    {
    int arr[] = {10,20,30,40,50,60};
    int *p=arr;
    printf("%d,%d,",*p++,*++p);
    printf("%d,%d,%d",*p,*p++,*++p);
    return 0;
    }

    为什么是 20,20,50,40,50. 我觉得的应该是 20,20,40,40,50 . 谁能解释下?

  3. #include <cstdio>
    #include <algorithm>

    struct LWPair{
    int l,w;
    };

    int main() {
    //freopen("input.txt","r",stdin);
    const int MAXSIZE=5000, MAXVAL=10000;
    LWPair sticks[MAXSIZE];
    int store[MAXSIZE];
    int ncase, nstick, length,width, tmp, time, i,j;
    if(scanf("%d",&ncase)!=1) return -1;
    while(ncase– && scanf("%d",&nstick)==1) {
    for(i=0;i<nstick;++i) scanf("%d%d",&sticks .l,&sticks .w);
    std::sort(sticks,sticks+nstick,[](const LWPair &lhs, const LWPair &rhs) { return lhs.l>rhs.l || lhs.l==rhs.l && lhs.w>rhs.w; });
    for(time=-1,i=0;i<nstick;++i) {
    tmp=sticks .w;
    for(j=time;j>=0 && store >=tmp;–j) ; // search from right to left
    if(j==time) { store[++time]=tmp; }
    else { store[j+1]=tmp; }
    }
    printf("%dn",time+1);
    }
    return 0;
    }