最少硬币问题
#include<iostream> #include<algorithm> using namespace std; int Min[251]; int type[5] = { 1, 5, 10, 25, 50 }; void solve(){ for (int i = 0; i < 251; i++){ Min[i] = INT_MAX; } Min[0] = 0; for (int j = 0; j < 5; j++){ for (int i = type[j]; i < 251; i++){ Min[i] = min(Min[i], Min[i - type[j]] + 1); } } } int main(){ int n; solve(); while (cin >> n){ cout << Min[n] << endl; } return 0; }最少硬币的组合 加上函数
void print_ans(int *Min_path,int s){ while (s){ cout << Min_path[s] << " "; s -= Min_path[s]; } cout << endl; }修改函数
void solve(){ for (int i = 0; i < 251; i++){ Min[i] = INT_MAX; } Min[0] = 0; for (int j = 0; j < 5; j++){ for (int i = type[j]; i < 251; i++){ if (Min[i] > Min[i - type[j]] + 1){ min_path[i] = type[j]; Min[i] = Min[i - type[j]] + 1; } } } } #include<iostream> #include<algorithm> using namespace std; int Min[251]; int type[5] = { 1, 5, 10, 25, 50 }; int min_path[251] = { 0 }; void solve(){ for (int i = 0; i < 251; i++){ Min[i] = INT_MAX; } Min[0] = 0; for (int j = 0; j < 5; j++){ for (int i = type[j]; i < 251; i++){ if (Min[i] > Min[i - type[j]] + 1){ min_path[i] = type[j]; Min[i] = Min[i - type[j]] + 1; } } } } void print_ans(int *Min_path,int s){ while (s){ cout << Min_path[s] << " "; s -= Min_path[s]; } cout << endl; } int main(){ int n; solve(); while (cin >> n){ cout << Min[n] << endl; print_ans(min_path, n); } return 0; }所有硬币组合
#include<iostream> using namespace std; int dp[251][101]; int type[5] = { 1, 5, 10, 25, 50 }; void solve(){ dp[0][0] = 1; for (int i = 0; i < 5; i++){ for (int j = 1; j <= 100; j++){ for (int k = type[i]; k <= 250; k++){ dp[k][j] += dp[k - type[i]][j - 1]; } } } } int main(){ int s; int ans[251] = {0}; solve(); for (int i = 0; i <= 250; i++){ for (int j = 0; j <= 100; j++){ ans[i] += dp[i][j]; } } while (cin >> s){ cout << ans[s] << endl; } return 0; }0/1背包
#include<iostream> using namespace std; int max(int x, int y){ return x > y ? x : y; } int main(){ int size, num; cin >> size >> num; int arr_size[31]; int map[30000] = {0}; for (int i = 1; i <= num; i++){ cin >> arr_size[i]; } for (int i = 1; i <= num; i++){ for (int j = size; j>=arr_size[i]; j--){ map[j] = max(map[j], map[j - arr_size[i]] + arr_size[i]); } } cout << size-map[size] << endl; return 0; }