多样的背包问题回顾

饭卡

Time Limit: 5000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)

Problem Description

电子科大本部食堂的饭卡有一种很诡异的设计，即在购买之前判断余额。如果购买一个商品之前，卡上的剩余金额大于或等于5元，就一定可以购买成功（即使购买后卡上余额为负），否则无法购买（即使金额足够）。所以大家都希望尽量使卡上的余额最少。
某天，食堂中有n种菜出售，每种菜可购买一次。已知每种菜的价格以及卡上的余额，问最少可使卡上的余额为多少。

Input

多组数据。对于每组数据：
第一行为正整数n，表示菜的数量。n<=1000。
第二行包括n个正整数，表示每种菜的价格。价格不超过50。
第三行包括一个正整数m，表示卡上的余额。m<=1000。

n=0表示数据结束。

Output

对于每组输入,输出一行,包含一个整数，表示卡上可能的最小余额。

Sample Input

1
50
5
10
1 2 3 2 1 1 2 3 2 1
50
0

Sample Output

-45
32

Source

UESTC 6th Programming Contest Online

const int maxn=1e4;
const int inf=99999999;
const double eps=1e-3;
const int lmt=1000;

int a[maxn],f[maxn];

int main()
{
    int n,m;
    while(~scanf("%d",&n))
    {
        if (!n) break;
        for(int i=1;i<=n;i++) scanf("%d",&a[i]);
        sort(a+1,a+n+1);
        scanf("%d",&m);
        if (m<5) 
        {
            printf("%d\n",m);continue;
        }
        CLEAR(f);
        int ans=0;
        for(int i=1;i<=n-1;i++)
        {
            for(int j=m-5;j-a[i]>=0;j--)

                    f[j]=max(f[j],f[j-a[i]]+a[i]);
        }
        cout<<m-a[n]-f[m-5]<<endl;
    }
    return 0;
}

Proud Merchants

Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 131072/65536 K (Java/Others)

Problem Description

Recently, iSea went to an ancient country. For such a long time, it was the most wealthy and powerful kingdom in the world. As a result, the people in this country are still very proud even if their nation hasn’t been so wealthy any more.
The merchants were the most typical, each of them only sold exactly one item, the price was Pi, but they would refuse to make a trade with you if your money were less than Qi, and iSea evaluated every item a value Vi.
If he had M units of money, what’s the maximum value iSea could get?

Input

There are several test cases in the input.

Each test case begin with two integers N, M (1 ≤ N ≤ 500, 1 ≤ M ≤ 5000), indicating the items’ number and the initial money.
Then N lines follow, each line contains three numbers Pi, Qi and Vi (1 ≤ Pi ≤ Qi ≤ 100, 1 ≤ Vi ≤ 1000), their meaning is in the description.

The input terminates by end of file marker.

Output

For each test case, output one integer, indicating maximum value iSea could get.

Sample Input

2 10
10 15 10
5 10 5
3 10
5 10 5
3 5 6
2 7 3

Sample Output

5
11

#define CLEAR(a,n) memset((a),0,n*sizeof((a)[0]))

const int maxn=510;
const int maxm=5010;

struct data
{
    int p,q,v;
    void read()
    {
        scanf("%d%d%d",&p,&q,&v);
    }
} item[maxn];

bool operator< (const data &a,const data &b)
{
    return a.q-a.p<b.q-b.p;//不是单纯地比较p！
}

int f[maxm];

int main()
{
    int n,m;

    while(~scanf("%d%d",&n,&m))
    {
        for(int i=1;i<=n;i++) item[i].read();
        sort(item+1,item+n+1);
        CLEAR(f,maxm);
        for(int i=1;i<=n;i++)
            for(int j=m;j>=item[i].q&&j>=item[i].p;j--)
                f[j]=max(f[j],f[j-item[i].p]+item[i].v);
        cout<<f[m]<<endl;
    }
    return 0;
}

ACboy needs your help

Time Limit: 1000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)

Problem Description

ACboy has N courses this term, and he plans to spend at most M days on study.Of course,the profit he will gain from different course depending on the days he spend on it.How to arrange the M days for the N courses to maximize the profit?

Input

The input consists of multiple data sets. A data set starts with a line containing two positive integers N and M, N is the number of courses, M is the days ACboy has.
Next follow a matrix A[i][j], (1<=i<=N<=100,1<=j<=M<=100).A[i][j] indicates if ACboy spend j days on ith course he will get profit of value A[i][j].
N = 0 and M = 0 ends the input.

Output

For each data set, your program should output a line which contains the number of the max profit ACboy will gain.

Sample Input

2 2
1 2
1 3
2 2
2 1
2 1
2 3
3 2 1
3 2 1
0 0

Sample Output

3
4
6

Source

HDU 2007-Spring Programming Contest

const int maxn=110;

int a[maxn][maxn],f[2][maxn];

int main()
{
    int n,m;
    while(~scanf("%d%d",&n,&m),n&&m)
    {
        for(int i=1;i<=n;i++)
            for(int j=1;j<=m;j++)
                scanf("%d",&a[i][j]);
        CLEAR(f[0],maxn);
        int cur=0;
        for(int i=1;i<=n;i++)
        {
            CLEAR(f[cur^1],maxn);
            for(int j=0;j<=m;j++)
                for(int k=0;k<=m-j;k++)
                    f[cur^1][j+k]=max(f[cur^1][j+k],f[cur][k]+a[i][j]);
            //for(int j=0;j<=m;j++)
                //f[0][j]=max(f[0][j],f[1][j]); 并非从前i-1的任何一步中滚过来
            cur^=1;
        }
        cout<<f[cur][m]<<endl;
    }
    return 0;
}

Consumer

Time Limit: 4000/2000 MS (Java/Others) Memory Limit: 32768/65536 K (Java/Others)

Problem Description
FJ is going to do some shopping, and before that, he needs some boxes to carry the different kinds of stuff he is going to buy. Each box is assigned to carry some specific kinds of stuff (that is to say, if he is going to buy one of these stuff, he has to buy the box beforehand). Each kind of stuff has its own value. Now FJ only has an amount of W dollars for shopping, he intends to get the highest value with the money.

Input

The first line will contain two integers, n (the number of boxes 1 <= n <= 50), w (the amount of money FJ has, 1 <= w <= 100000) Then n lines follow. Each line contains the following number pi (the price of the ith box 1<=pi<=1000), mi (1<=mi<=10 the number goods ith box can carry), and mi pairs of numbers, the price cj (1<=cj<=100), the value vj(1<=vj<=1000000)

Output

For each test case, output the maximum value FJ can get

Sample Input

3 800
300 2 30 50 25 80
600 1 50 130
400 3 40 70 30 40 35 60

Sample Output

210

LL f[2][maxn];
int p[maxn],m[maxn],c[maxn],v[maxn];

int main()
{
    int n,w,sum;
    while(~scanf("%d%d",&n,&w))
    {
        //if (!n&&!w) break;
        sum=0;
        for(int i=1;i<=n;i++)
        {
            scanf("%d%d",&p[i],&m[i]);
            for(int j=sum+1;j<=sum+m[i];j++) scanf("%d%d",&c[j],&v[j]);
            sum+=m[i];
        }
        //for(int i=1;i<=sum;i++) cout<<c[i]<<' '<<v[i]<<endl;

        CLEAR(f);
        sum=0;
        bool cur=0;
        for(int i=1;i<=n;i++)
        {
            for(int j=0;j<=w-p[i];j++) f[cur^1][j+p[i]]=f[cur][j];
            for(int k=1;k<=m[i];k++)
            for(int j=w;j>=c[sum+k]+p[i];j--)
            {
                    f[cur^1][j]=max(f[cur^1][j],f[cur^1][j-c[sum+k]]+(LL)v[sum+k]);
            }
            for(int j=w;j>=p[i];j--)
                f[cur][j]=max(f[cur][j],f[cur^1][j]);
            sum+=m[i];
            //cur^=1;
        }
        int ans=0;
        //for(int j=0;j<=w;j++) cout<<f[cur^1][j]<<' ';cout<<endl;//ans=max(ans,f[cur][j]);
        //for(int j=0;j<=w;j++) cout<<f[cur][j]<<' ';cout<<endl;
        cout<<f[cur][w]<<endl;
    }
    return 0;
}

The more, The Better

Time Limit: 6000/2000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)

Problem Description

ACboy很喜欢玩一种战略游戏，在一个地图上，有N座城堡，每座城堡都有一定的宝物，在每次游戏中ACboy允许攻克M个城堡并获得里面的宝物。但由于地理位置原因，有些城堡不能直接攻克，要攻克这些城堡必须先攻克其他某一个特定的城堡。你能帮ACboy算出要获得尽量多的宝物应该攻克哪M个城堡吗？

Input

每个测试实例首先包括2个整数，N,M.(1 <= M <= N = 0。当N = 0, M = 0输入结束。

Output

对于每个测试实例，输出一个整数，代表ACboy攻克M个城堡所获得的最多宝物的数量。

Sample Input

3 2
0 1
0 2
0 3
7 4
2 2
0 1
0 4
2 1
7 1
7 6
2 2
0 0

Sample Output

5
13

Author

8600

Source

HDU 2006-12 Programming Contest

const int maxn=210;

struct Edge
{
    int to,next;
    Edge(){}
    Edge(int v,int w):to(v),next(w){}
} edge[maxn];
int head[maxn];
int ve[maxn];
int n,m;
int f[maxn][maxn];

void addedge(int u,int v)
{
    edge[head[0]]=Edge(v,head[u]);
    head[u]=head[0]++;
}

void init()
{
    memset(head,-1,maxn*sizeof(head[0]));
    head[0]=1;
    ve[1]=0;
}

void dfs(int u)
{
    CLEAR(f[u],maxn);
    f[u][0]=ve[u];
    for(int i=head[u];i>-1;i=edge[i].next)
    {
        int v=edge[i].to;
        dfs(v);
        //for(int j=1;j<=m;j++) 密切关注状态转移方向和范围
            //for(int k=1;k<=m-j;k++)
                //f[u][j+k]=max(f[u][j+k],f[u][k]+f[v][j]);
        for(int j=m;j>0;j--)
            for(int k=1;k<=j;k++)
                f[u][j]=max(f[u][j],f[u][j-k]+f[v][k-1]);
        //cout<<u<<'-'<<v<<' '<<f[u][m]<<endl;
    }
    //for(int j=0;j<=m;j++) f[u][j]+=ve[u];边界条件
}

int main()
{

    while(~scanf("%d%d",&n,&m),n&&m)
    {
        init();
        for(int i=1;i<=n;i++)
        {
            int a,b;
            scanf("%d%d",&a,&b);
            addedge(a+1,i+1);
            ve[i+1]=b;
        }
        dfs(1);
        cout<<f[1][m]<<endl;
    }
    return 0;
}

Gold miner

Time Limit: 4000/2000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)

Problem Description

Homelesser likes playing Gold miners in class. He has to pay much attention to the teacher to avoid being noticed. So he always lose the game. After losing many times, he wants your help.

To make it easy, the gold becomes a point (with the area of 0). You are given each gold’s position, the time spent to get this gold, and the value of this gold. Maybe some pieces of gold are co-line, you can only get these pieces in order. You can assume it can turn to any direction immediately.
Please help Homelesser get the maximum value.

Input

There are multiple cases.
In each case, the first line contains two integers N (the number of pieces of gold), T (the total time). (0＜N≤200, 0≤T≤40000)
In each of the next N lines, there four integers x, y (the position of the gold), t (the time to get this gold), v (the value of this gold). (0≤|x|≤200, 0＜y≤200,0＜t≤200, 0≤v≤200)

Output

Print the case number and the maximum value for each test case.

Sample Input

3 10
1 1 1 1
2 2 2 2
1 3 15 9
3 10
1 1 13 1
2 2 2 2
1 3 4 7

Sample Output

Case 1: 3
Case 2: 7

Author

HIT

Source

2012 Multi-University Training Contest 5

int dblcmp(double d)
{
    if (fabs(d)<eps) return 0;
    else return (d>0)?1:-1;
}

struct data
{
    int x,y,t,v;
    data(){x=y=t=v=0;};
    data(int _x,int _y,int _t,int _v):x(_x),y(_y),t(_t),v(_v){};
    void prt()
    {
        cout<<x<<' '<<y<<' '<<t<<' '<<v<<endl;
    }
} gold[maxn];

int dist(data a)
{
    return a.x*a.x+a.y*a.y;
}

bool operator< (const data &a,const data &b)
{
    if (dblcmp(a.x * b.y - b.x * a.y)==0) return dist(a)<dist(b);
    return dblcmp(a.x * b.y - b.x * a.y)>0;
    //if (dist(a)==dist(b)) return dblcmp(a.x * b.y - b.x * a.y);
    //return dist(a)<dist(b);
}

bool operator== (const data &a,const data &b)
{
    return dblcmp(a.x * b.y - b.x * a.y)==0;
}

bool operator!= (const data &a,const data &b)
{
    return !(a==b);
}


typedef vector<data> vec;
typedef map<int,vec> hashmap;
hashmap mp;

int f[maxl];
vec vc[maxn];

int main()
{
    int n,m,kase=0;
    while(~scanf("%d%d",&n,&m))
    {
        mp.clear();
        for(int i=1;i<=n;i++)
        {
            int x,y,t,v;
            scanf("%d%d%d%d",&x,&y,&t,&v);
            gold[i]=data(x,y,t,v);

        }
        //puts("--");
        sort(gold+1,gold+n+1);
        int cnt=1;
        vc[cnt].clear();
        for(int i=1;i<=n;i++)
        {
            if (vc[cnt].size())
            {
                data tmp=vc[cnt][vc[cnt].size()-1];
                gold[i]=data(gold[i].x,gold[i].y,gold[i].t+tmp.t,gold[i].v+tmp.v);
            }
            vc[cnt].push_back(gold[i]);
            if (gold[i]!=gold[i+1]) vc[++cnt].clear();
        }
        CLEAR(f);
        /*for(int k=1;k<=cnt;k++)
        {
            for(int i=0;i<vc[k].size();i++)
                vc[k][i].prt();
                puts("-");
        }*/

        for(int k=1;k<=cnt;k++)
            for(int j=m;j>=0;j--)
            for(int i=0;i<vc[k].size();i++)
                if (j>=vc[k][i].t)
                    f[j]=max(f[j],f[j-vc[k][i].t]+vc[k][i].v);



        printf("Case %d: %d\n",++kase,f[m]);
    }
    return 0;
}

Beam Cannon

Time Limit: 3000/1500 MS (Java/Others) Memory Limit: 65536/65536 K (Java/Others)

Problem Description

Recently, the γ galaxies broke out Star Wars. Each planet is warring for resources. In the Star Wars, Planet X is under attack by other planets. Now, a large wave of enemy spaceships is approaching. There is a very large Beam Cannon on the Planet X, and it is very powerful, which can destroy all the spaceships in its attack range in a second. However, it takes a long time to fill the energy of the Beam Cannon after each shot. So, you should make sure each shot can destroy the enemy spaceships as many as possible.
To simplify the problem, the Beam Cannon can shot at any area in the space, and the attack area is rectangular. The rectangle parallels to the coordinate axes and cannot rotate. It can only move horizontally or vertically. The enemy spaceship in the space can be considered as a point projected to the attack plane. If the point is in the rectangular attack area of the Beam Cannon(including border), the spaceship will be destroyed.

Input

Input contains multiple test cases. Each test case contains three integers N(1<=N<=10000, the number of enemy spaceships), W(1<=W<=40000, the width of the Beam Cannon’s attack area), H(1<=H<=40000, the height of the Beam Cannon’s attack area) in the first line, and then N lines follow. Each line contains two integers x,y (-20000<=x,y<=20000, the coordinates of an enemy spaceship).
A test case starting with a negative integer terminates the input and this test case should not to be processed.

Output

Output the maximum number of enemy spaceships the Beam Cannon can destroy in a single shot for each case.

Sample Input

2 3 4
0 1
1 0
3 1 1
-1 0
0 1
1 0
-1

Sample Output

2
2

Source

2014上海全国邀请赛——题目重现（感谢上海大学提供题目）

FATE

Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)

Problem Description

最近xhd正在玩一款叫做FATE的游戏，为了得到极品装备，xhd在不停的杀怪做任务。久而久之xhd开始对杀怪产生的厌恶感，但又不得不通过杀怪来升完这最后一级。现在的问题是，xhd升掉最后一级还需n的经验值，xhd还留有m的忍耐度，每杀一个怪xhd会得到相应的经验，并减掉相应的忍耐度。当忍耐度降到0或者0以下时，xhd就不会玩这游戏。xhd还说了他最多只杀s只怪。请问他能升掉这最后一级吗？

Input

输入数据有多组，对于每组数据第一行输入n，m，k，s(0 < n,m,k,s < 100)四个正整数。分别表示还需的经验值，保留的忍耐度，怪的种数和最多的杀怪数。接下来输入k行数据。每行数据输入两个正整数a，b(0 < a,b < 20)；分别表示杀掉一只这种怪xhd会得到的经验值和会减掉的忍耐度。(每种怪都有无数个)

Output

输出升完这级还能保留的最大忍耐度，如果无法升完这级输出-1。

Sample Input

10 10 1 10
1 1
10 10 1 9
1 1
9 10 2 10
1 1
2 2

Sample Output

0
-1
1

Author

Xhd

int f[maxn][maxn];//exp,sum
int v[maxn],w[maxn];

int main()
{
    int n,m,st,K;
    while(~scanf("%d%d%d%d",&st,&m,&n,&K))
    {
        for(int i=1;i<=n;i++)
            scanf("%d%d",&v[i],&w[i]);
        memset(f,0,sizeof(f));
        for(int i=1;i<=n;i++)
            //for(int j=m;j>=0;j--)
            for(int j=w[i];j<=m;j++)
                for(int k=1;k<=K;k++)
                    f[j][k]=max(f[j][k],f[j-w[i]][k-1]+v[i]);
        /*int ans=0;
        for(int i=1;i<=K;i++) ans=max(ans,f[0][i]);
        if (ans<st) printf("-1\n");
        else printf("%d\n",ans);*/
        bool ans=0;
        for(int i=1;i<=m;i++)
            if (f[i][K]>=st)
        {
            ans=1;
            printf("%d\n",m-i);
            break;
        }
        if (!ans) printf("-1\n");
    }
    return 0;
}