0-1背包
网上看了题解后才了解,把价值当作容量。可以简化这个问题。
#include<cstdio> #include<iostream> #include<cstring> using namespace std; #define INF 10000001 int dp[10003];//dp[i] 表示i价值最少能用掉多少座位 int n,m,k; int min(int a,int b) { return a<b?a:b; } int cal(int i,int w) { int num=i/k+1; if(w+i<=num*k) return i+w; else return num*k+w; } int main() { int t; int i,j; int w,v; cin>>t; while(t--) { cin>>n>>m>>k; for(i=1;i<=10000;i++) dp[i]=INF; dp[0]=0; for(i=0;i<n;i++) { cin>>w>>v; w++;//加上总统 for(j=10000;j>=v;j--) if(dp[j-v]!=INF) dp[j]=min(dp[j],cal(dp[j-v],w)); } //for(i=0;i<=100;i++) // cout<<dp[i]<<endl; int ans=10000; while(dp[ans]>k*m) { ans--; } cout<<ans<<endl; } return 0; }