#include<iostream> #include<cstring> #include<cmath> #include<algorithm> #include<iomanip> using namespace std; int dp[1200][1200]; int a[1200]; int main() { int n;//n个菜 int yue; int sum; int f1,f2; while(cin>>n&&n!=0) { sum=0; memset(a,0,sizeof(a)); memset(dp,0,sizeof(dp)); for(int i=1;i<=n;i++) { cin>>a[i]; } cin>>yue; if(yue<5) cout<<yue<<endl; else { sort(a+1,a+n+1); sum=yue-5; for(int i=1;i<=n-1;i++) { for(int j=0;j<=sum;j++) { if(j>=a[i]) { dp[i][j] = max(dp[i-1][j], dp[i-1][j-a[i]]+a[i]); } else dp[i][j] = dp[i-1][j]; } } yue=yue-dp[n-1][sum]-a[n]; cout<<yue<<endl; } } return 0; }
原文:https://www.cnblogs.com/sakuraXiYue/p/9032729.html