求每次能获得的最大利润，多重背包。
这里要用到一个技巧，题目说了v[i]是1000的倍数，所以可以都除以1000
代码如下：
#include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include using namespace std; typedef long long LL; const int N=51510; const LL II=1000000007; int dp[N],v[15],w[15]; int V,y,n; int main() { int n,i,j,k,l,t; cin>>n; while(n--) { scanf("%d%d%d",&V,&y,&t); for(i=1;i<=t;i++) { scanf("%d%d",&v[i],&w[i]); v[i]/=1000; } for(l=1;l<=y;l++) { int temp=V/1000; memset(dp,0,sizeof(dp)); for(i=1;i<=t;i++) { for(j=v[i];j<=temp;j++) //多重背包 j=v[i];j<=temp;j++ //01背包 j=temp;j>=v[i];j-- if(dp[j] #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include using namespace std; typedef long long LL; const int N=51510; const LL II=1000000007; int dp[N],v[15],w[15]; int V,y,n; int main() { int n,i,j,k,l,t; cin>>n; while(n--) { scanf("%d%d%d",&V,&y,&t); for(i=1;i<=t;i++) { scanf("%d%d",&v[i],&w[i]); v[i]/=1000; } for(l=1;l<=y;l++) { int temp=V/1000; memset(dp,0,sizeof(dp)); for(i=1;i<=t;i++) { for(j=v[i];j<=temp;j++) //多重背包 j=v[i];j<=temp;j++ //01背包 j=temp;j>=v[i];j-- if(dp[j]