HDOJ(HDU).2159 FATE (DP 带个数限制的完全背包)

题意分析

与普通的完全背包大同小异，区别就在于多了一个个数限制，那么在普通的完全背包的基础上，增加一维，表示个数。同时for循环多写一层即可。

#include <iostream>

#include <cstdio>

#include <cstring>

#include <algorithm>

#define nmax 105

using namespace std;

int dp[nmax][nmax];

struct item{

    int exp;

    int ence;

    double rate;

}a[nmax];

bool cmp(item a, item b)

{

    return a.rate>b.rate;

}

void output(int n, int m)

{

    printf("--------------DEBUG--------------\n");

    for(int i = 0;i<=10;++i){

        for(int j = 0 ;j<=10 ;++j) {

            printf("%3d",dp[i][j]);

        }

        printf("\n");

    }

    printf("--------------DEBUG--------------\n");

}

int main()

{

    //freopen("in.txt","r",stdin);

    int n,m,k,s;

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

        memset(dp,0,sizeof(dp));

        for(int i =1; i<=k; ++i) {scanf("%d %d",&a[i].exp,&a[i].ence); a[i].rate = a[i].exp / a[i].ence;}

        //sort(a+1,a+1+k,cmp);

        for(int i =1; i<=k; ++i) {

            for(int j = a[i].ence; j<=m; ++j)

                for(int l = 1; l<=s;++l)

                    dp[j][l] = max(dp[j][l],dp[j-a[i].ence][l-1] +a[i].exp);

        }

        //output(k,s);

        //printf("%d %d %d\n",m,s,n);

        if(dp[m][s]>=n){

            for(int i =0;i<=m;++i)

                if(dp[i][s]>=n){

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

                    break;

                }

        }else{

            printf("-1\n");

        }

    }

    return 0;

}