#include #include #include #include #include #include #include #include #define inf 0x3f3f3f3f #define ll __int64 using namespace std; int n,m,dp[100010],a[100010],c[1010]; void pack01(int cost,int w) { for(int i=m;i>=cost;i--) dp[i]=max(dp[i-cost]+w,dp[i]); } void packall(int cost,int w) { for(int i=cost;i<=m;i++) dp[i]=max(dp[i-cost]+w,dp[i]); } void multipack(int cost,int w,int cnt) { if(cost*cnt>=m)//体积乘以数量大于总体积，说明不能完全装完，相当于有无穷件，用完全背包 packall(cost,w); else //可以装完，用01背包 { int i=1; while(i