与普通的完全背包大同小异，区别就在于多了一个个数限制，那么在普通的完全背包的基础上，增加一维，表示个数。同时for循环多写一层即可。
#include <iostream>#include <cstdio>#include <cstring>#include <algorithm>#define nmax 105using 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;}新闻热点
疑难解答
