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;
}