题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=2546
问题描述：
解法：
首先明显知道每一次的决策都会对后面的结果造成影响，所以很容易想到这是一个 DP 问题
然后每个物品只能取一次 ，那么会往 01背包上去考虑
首先最大的那个物品我们肯定是希望可以直接减掉的（因为这样可以保证最小）
那么我们先进行排序
然后现在的问题就变成了：如何从前 n-1 个物品里面选出体积为m-5的最大价值 x
然后用m-x-a[n] 就是最后答案
#include <iostream> #include <algorithm> #include <string> #include <string.h> #include <vector> #include <map> #include <stack> #include <set> #include <queue> #include <math.h> #include <cstdio> #include <iomanip> #include <time.h> #define LL long long #define INF 0x3f3f3f3f #define ls nod<<1 #define rs (nod<<1)+1 #define cin std::cin #define cout std::cout #define endl std::endl; const int maxn = 1e5 + 10; int n,m; int dp[1010],w[1010]; int main() { while (cin >> n) { if (n == 0) break; for (int i = 1;i <= n;i++) { cin >> w[i]; } cin >> m; if (m < 5) { cout << m << endl; continue; } memset(dp,0, sizeof(dp)); std::sort(w+1,w+1+n); for (int i = 1;i < n;i++) { for (int j = m-5;j >= w[i];j--) dp[j] = std::max(dp[j],dp[j-w[i]]+w[i]); } printf("%d\n",m-dp[m-5]-w[n]); } return 0; }
原文：https://www.cnblogs.com/-Ackerman/p/12253268.html