团体程序设计天梯赛
L3-001 凑零钱
第二种方法是动态规划。这是01背包问题。背包容量是允许的零钱价值最大和。假如这个背包容量是100，指的是，最大能放到背包中的零钱价值总和是100，目的也是最大化放进背包的这个价值总和。所以当为有解的情况，背包里零钱的价值总和恰好是100. 将所有硬币按价值从大到小排序，使用一维背包dp迭代，并使用二维布尔数组choice记录每次迭代中更新的记录。若算法结束dp[m]恰好等于m，则说明有解，将choice数组从右下到左上进行状态转移，输出最终结果。（如果使用二维背包应该不需要开choice数组，可以试一试。）
动态规划（Dynamic Programming）
- 定义状态
- 设计状态转移方程
- 设定初始状态
- 执行状态转移
- 输出解
01背包问题，可以参考：AcWing 2. 01背包问题（状态转移方程讲解） by深蓝
#include <bits/stdc++.h>
using namespace std;
vector<int> val, dp;
vector<vector<bool> > choice;
bool cmp(int a, int b){return a > b;}
int main(){
int n, m;
cin >> n >> m;
val.resize(n);
dp.resize(m + 1);
choice.resize(n);
for(int i = 0; i <= n - 1; i++) choice[i].resize(m + 1);
for(int i = 0; i <= n - 1; i++) cin >> val[i];
sort(val.begin(), val.end(), cmp);
for(int i = 0; i <= n - 1; i++){
for(int j = m; j >= val[i]; j--){
if(dp[j] <= dp[j - val[i]] + val[i]){
dp[j] = dp[j - val[i]] + val[i];
choice[i][j] = 1;
}
}
}
if(dp[m] != m) cout << "No Solution" << endl;
else{
int cap = m, flag = 0;
for(int i = n - 1; i >= 0; i--){
if(cap <= 0) break;
if(choice[i][cap]){
if(!flag){
flag++;
cout << val[i];
}
else cout << ' ' << val[i];
cap -= val[i];
}
else continue;
}
cout << endl;
}
return 0;
}