多重背包,很水
#include<stdio.h> #include<cstdio> #include<iostream> #include<algorithm> #include<math.h> #include<stdlib.h> #include<string.h> #include<string> #include<queue> #include<map> #define LL long long #define INF 0xfffffff #define MAX(a,b) a>b?a:b #define MIN(a,b) a<b?a:b using namespace std; int dp[150][150]; int v[150],w[150]; int main() { int n,m,k,s; while(scanf("%d%d%d%d",&n,&m,&k,&s)!=EOF) { int ans = -1; memset(dp,0,sizeof(dp)); for(int i=1;i<=k;i++) { scanf("%d%d",&v[i],&w[i]); } for(int q=1;q<=s;q++) { for(int i=1;i<=k;i++) { for(int j=w[i];j<=m;j++) { dp[q][j] = max(dp[q][j],dp[q-1][j-w[i]]+v[i]); if(dp[q][j] >= n) { ans = max(ans,m-j); } } } } printf("%d\n",ans); } return 0; }View Code