hdu1864/2844/2159 背包基础题

hdu1864 01背包

题目大意：一堆数，找到一个最大的和满足这个和不超过Q
要学会分析复杂度！

#include <cstdio>

#include <cstring>

#define MAX(a,b) (a>b?a:b)

const int N = ;

int dp[N],data[N];

float bound;

int n,cnt;

int main(){

    char type;

    float price[],tprice;

    while(scanf("%f%d",&bound,&n)&&n){

        int totalCnt = ;

        for(int i=;i<n;i++){

            scanf("%d",&cnt);

            bool flag = true;

            price[]=price[]=price[]=0.0f;

            for(int j=;j<cnt;j++){

                getchar();

                scanf("%c:%f",&type,&tprice);

                if((type!='A')&&(type!='B')&&(type!='C')) flag = false;

                else price[type-'A'] += tprice;

            }

            if(!flag) continue;

            if(price[]>||price[]>||price[]>) continue;

            float totalPrice = price[]+price[]+price[];

            if(totalPrice>) continue;

            data[totalCnt++] = (totalPrice*);

        }

        memset(dp,,sizeof(dp));

        bound*=;

        for(int i=;i<totalCnt;i++)

            for(int v=bound;v>=data[i];v--)

                dp[v] = MAX(dp[v],dp[v-data[i]]+data[i]);

        printf("%.2f\n",dp[bound]/);

    }

    return ;

}

hdu2844 多重背包模板题

题目链接

题目大意：两个数组A,C。表示有Ci个Ai，问1-m中有多少个数能由这堆数相加表示。

#include <set>

#include <map>

#include <stack>

#include <queue>

#include <cmath>

#include <vector>

#include <string>

#include <cstdio>

#include <cstring>

#include <cstdlib>

#include <iostream>

#include <algorithm>

#define MAX(a,b) ((a)>=(b)?(a):(b))

#define MIN(a,b) ((a)<=(b)?(a):(b))

#define OO 0x0fffffff

using namespace std;

const int N = ;

int f[N],A[],C[];

int main(){

    int n,m;

    int tcnt,tcv;

    while(scanf("%d%d",&n,&m),m+n){

        memset(f,,sizeof(f));

        for(int i=;i<n;i++) cin>>A[i];

        for(int i=;i<n;i++) cin>>C[i];

        for(int i=;i<n;i++){

            tcnt = ;

            while(C[i]){

                tcv=tcnt*A[i];

                for(int v=m;v>=tcv;v--)

                    f[v] = MAX(f[v],f[v-tcv]+tcv);

                C[i]-=tcnt;

                if((tcnt<<)<=C[i]) tcnt<<=;

                else tcnt=C[i];

            }

        }

        int ans = ;

        for(int i=;i<=m;i++) if(f[i]==i) ans++;

        printf("%d\n",ans);

    }

    return ;

}

hdu2159 完全背包

题目链接

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

/********************************************************/

二维费用的完全背包

#include <set>

#include <map>

#include <stack>

#include <queue>

#include <cmath>

#include <vector>

#include <string>

#include <cstdio>

#include <cstring>

#include <cstdlib>

#include <iostream>

#include <algorithm>

#define MAX(a,b) ((a)>=(b)?(a):(b))

#define MIN(a,b) ((a)<=(b)?(a):(b))

#define OO 0x0fffffff

using namespace std;

const int N = ;

int f[N][N],value[N],cost[N];

int main(){

    int n,m,k,s;

    while(scanf("%d%d%d%d",&n,&m,&k,&s)!=EOF){

        for(int i=;i<k;i++) scanf("%d%d",value+i,cost+i);

        memset(f,,sizeof(f));

        for(int i=;i<k;i++) for(int x=cost[i];x<=m;x++)

        for(int y=;y<=s;y++){

            f[x][y] = MAX(f[x][y],f[x-cost[i]][y-]+value[i]);

        }

        if(f[m][s]<n){

            puts("-1");

            continue;

        }

        for(int x=;x<=m;x++){

            if(f[x][s]>=n){

                printf("%d\n",m-x);

                break;

            }

        }

    }

    return ;

}

巴特西

hdu1864/2844/2159 背包基础题

最新文章

热门文章