感觉用背包去想反而麻烦。。就是一个递推
#include #include #include #include #include #include #include #include #define inf 0x3f3f3f3f #define ll __int64 using namespace std; int n,v,k,s,dp[110][110],w[110],c[110]; int main() { int i,j,p; while(~scanf("%d%d%d%d",&n,&v,&k,&s)) { for(i=1;i<=k;i++) scanf("%d%d",&w[i],&c[i]); memset(dp,0,sizeof dp); for(i=1;i<=v;i++)//背包容量 { for(j=1;j<=k;j++)//几种物品 { for(p=1;p<=s;p++)//选几样 { if(i>=c[j]) dp[i][p]=max(dp[i][p],dp[i-c[j]][p-1]+w[j]); } } } if(dp[v][s] =0;i--) { // printf("i:%d dpis:%d\n",i,dp[i][s]); if(dp[i][s]