题目:给你一些钱币和一个价格,用钱币组成不小于价格的最低值,并使得此时使用的钱币总数最少。
分析:dp,01背包。初始化所有的的钱数组成都需要Max张钱币,F[0] = 0,更新即可。
因为,可以取超过price的值,所以将背包的容量扩大一些,找到最接近的即可。
说明:找零钱用背包。
#include <iostream>
#include <cstdlib>
using namespace std;
int F[20001];
int C[101];
int main()
{
int t,p,n,sum;
while (cin >> t)
while (t --) {
cin >> p >> n;
sum = 0;
for (int i = 0 ; i < n ; ++ i) {
cin >> C[i];
if (sum < p) sum += C[i];
}
for (int i = 1 ; i <= sum ; ++ i)
F[i] = n;
F[0] = 0;
for (int i = 0 ; i < n ; ++ i)
for (int j = sum ; j >= C[i] ; -- j)
if (F[j] > F[j-C[i]]+1)
F[j] = F[j-C[i]]+1;
int s = p;
while (s < sum && F[s] == n) s ++;
cout << s << " " << F[s] << endl;
}
return 0;
}