dp，答案容易想到是 凑出价格总和≤m-5 + 没被使用的最大价格。
dp[i = 前i种价格][j = 价格总和] = 最大没使用的价格下标idx_m。
dp[i-1][j]存在的话，则只要更新idx_m。
如果dp[i-1][j-c[i]]存在但是dp[i-1][j]不存在，那么c[i]必须使用，idx不变。
把价格从小到大排序更容易写。
/** alfs x kayi */ #include<bits/stdc++.h> using namespace std; typedef long long ll; const int maxn = 1e3+1; int c[maxn]; int dp[maxn]; int n, m; int solve() { if(m < 5) { return m; } int lm = m-5, i; memset(dp+1,-1,sizeof(int)*lm); sort(c+1,c+n+1); dp[0] = 0; c[0] = 0; for(i = 1; i <= n; i++){ for(int j = lm; j>=c[i]; j--){ if(~dp[j-c[i]]){ dp[j] = ~dp[j]? i : dp[j-c[i]]; } } for(int j = c[i]-1; j >= 0; j--){ if(~dp[j]) dp[j] = i; } } int ans = m ; for(i = 0; i <= lm; i++){ if(~dp[i]){ ans = min(ans, m-i-c[dp[i]]); } } return ans; } //#define LOCAL int main() { #ifdef LOCAL freopen("in.txt","r",stdin); #endif while(scanf("%d",&n),n){ for(int i = 1; i <= n; i++){ scanf("%d", c+i); } scanf("%d", &m); printf("%d\n", solve()); } return 0; }
原文：http://www.cnblogs.com/jerryRey/p/5002376.html