饭卡

Time Limit: 5000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 32818 Accepted Submission(s): 11344

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

Code

#include<iostream>
#include<cstring> 
#include<algorithm>
using namespace std;
int food[2001];
int dp[2001];
int cmp(int a,int b){
    return a<b;
}
int main(){
    int T;//菜的数量 
    while(cin>>T && T!=EOF)
    {
        int money;
        memset(food,0,sizeof(food));
        if(T==0) break;
        else
        {
            for(int i=0;i<T;i++)
            {
                cin>>food[i];
            }
            money=0;cin>>money;
            memset(dp,0,sizeof(dp)); 
            if(money<5){
                cout<<money<<endl;
                continue;
            }
            else
            {
                money-=5;
                sort(food,food+T,cmp);
//                if(money>=food[0]){
                    for(int i=0;i<T-1;i++)
                    {
                        for(int j=money;j>=food[i];j--)
                        {
                            dp[j]=max(dp[j],dp[j-food[i]]+food[i]); //空间优化 
                        }
                    }
//                }
            }
        }
        cout<<money+5-dp[money]-food[T-1]<<endl;
    }
    return 0;
}

Big Event in HDU

Time Limit: 10000/5000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others)
Total Submission(s): 43795 Accepted Submission(s): 15066

Problem Description

Nowadays, we all know that Computer College is the biggest department in HDU. But, maybe you don't know that Computer College had ever been split into Computer College and Software College in 2002.
The splitting is absolutely a big event in HDU! At the same time, it is a trouble thing too. All facilities must go halves. First, all facilities are assessed, and two facilities are thought to be same if they have the same value. It is assumed that there is N (0<N<1000) kinds of facilities (different value, different kinds).

Input

Input contains multiple test cases. Each test case starts with a number N (0 < N <= 50 -- the total number of different facilities). The next N lines contain an integer V (0<V<=50 --value of facility) and an integer M (0<M<=100 --corresponding number of the facilities) each. You can assume that all V are different.
A test case starting with a negative integer terminates input and this test case is not to be processed.

Output

For each case, print one line containing two integers A and B which denote the value of Computer College and Software College will get respectively. A and B should be as equal as possible. At the same time, you should guarantee that A is not less than B.

Sample Input

Sample Output

20 10
40 40

Code

#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
typedef long long ll;


int main(){
    int N;
    while(cin>>N && N>0){
        ll sum=0;//价值总量 
        int count;//物品数量 
        int V[10001];
        int dp[125025]; //数组开小了会RE
        memset(V,0,sizeof(V));
        memset(dp,0,sizeof(dp));
        int i,j;
        for(i=0,j=0;i<N;i++)
        {
            int a,b;
            cin>>a>>b;
            count+=b;
            while(b--)
            {
                V[j++]=a;
                sum+=a;
            }
        }
        ll sum2=sum/2;
        for(int i=0;i<count;i++)
        {
            for(int j=sum2;j>=V[i];j--)
            {
                dp[j]=max(dp[j],dp[j-V[i]]+V[i]);
            }
        }
        cout<<sum-dp[sum2]<<" "<<dp[sum2]<<endl;
    }
}

Bone Collector

Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 66293 Accepted Submission(s): 27654

Problem Description

Many years ago , in Teddy’s hometown there was a man who was called “Bone Collector”. This man like to collect varies of bones , such as dog’s , cow’s , also he went to the grave …
The bone collector had a big bag with a volume of V ,and along his trip of collecting there are a lot of bones , obviously , different bone has different value and different volume, now given the each bone’s value along his trip , can you calculate out the maximum of the total value the bone collector can get ?
小白算法练习简单背包问题专题001 hdu 01背包 dp

Input

The first line contain a integer T , the number of cases.
Followed by T cases , each case three lines , the first line contain two integer N , V, (N <= 1000 , V <= 1000 )representing the number of bones and the volume of his bag. And the second line contain N integers representing the value of each bone. The third line contain N integers representing the volume of each bone.

Output

One integer per line representing the maximum of the total value (this number will be less than 2³¹).

Sample Input

Sample Output

14

Code

#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;

int main(){
    int T;
    cin>>T;
    while(T--)
    {
        int v[10010]={0};
        int w[10010]={0};
        int dp[20002]={0};
        int N,M;
        cin>>N>>M;
        for(int i=0;i<N;i++)
        {
            cin>>w[i];
        }
        for(int i=0;i<N;i++)
        {
            cin>>v[i];
        }
        for(int i=0;i<N;i++)
        {
            for(int j=M;j>=v[i];j--)
            {
                dp[j]=max(dp[j],dp[j-v[i]]+w[i]);
            }
        }
        cout<<dp[M]<<endl;
    }
    return 0;
}

小白算法练习 简单背包问题专题001 hdu 01背包 dp

饭卡

Big Event in HDU

Bone Collector

相关推荐

小白算法练习简单背包问题专题001 hdu 01背包 dp