这是我们15级新生热身赛的题目，当时很少新生做出来，不仅因为当时还没有学dp，也因为这不是小白完全背包，这里给出了一个值m，让我们选取一定的物品让他们的价值>=m，让我们求最小值花费。
首先明确m并不能作为背包容量，因为我们的价值可能大于m，其实让我们求最小花费，我们无疑在一开始就要把dp初始化为无穷大，这样就自然给了一个标记，所以我们必须要找到那个正好装满的点，那个点的值才是我们要的答案，其实方法很简单，只要适当的扩增这个背包的容量，假如扩大K，那在（m，m+k）之间排个序，找到最小值就可以了。这里的k就是这些物品中的最大价值，因为如果装不满，在加上这个肯定够了
现在再回头看看自己一开始的题，现在才写出这篇博客，感觉自己真的有所成长，有所收获，所以继续努力吧～
#include<iostream> #include<cstdio> #include<cstring> #include<cmath> #include<algorithm> using namespace std; int main() { int t; scanf("%d",&t); while(t--) { int n,m; scanf("%d%d",&n,&m); int c[200],w[200]; long long f[2200]; for(int i = 1; i <= n; i++) { scanf("%d%d",&c[i],&w[i]); } for(int i = 1;i <= m + 1000;i++) f[i] = 999999999; f[0] = 0; for(int i = 1; i <= n; i++) { for(int j = w[i]; j <= m + 1000; j++) if(f[j-w[i]] + c[i] < f[j]) f[j] = f[j-w[i]] + c[i]; } sort(f+m,f+m+1000); cout<<f[m]<<endl; } }
原文：http://www.cnblogs.com/jifahu/p/5543496.html