(持续更新)
奇怪的汉诺塔(4柱汉诺塔)
描述
汉诺塔问题，条件如下：
1、这里有A、B、C和D四座塔。
2、这里有n个圆盘，n的数量是恒定的。
3、每个圆盘的尺寸都不相同。
4、所有的圆盘在开始时都堆叠在塔A上，且圆盘尺寸从塔顶到塔底逐渐增大。
5、我们需要将所有的圆盘都从塔A转移到塔D上。
6、每次可以移动一个圆盘，当塔为空塔或者塔顶圆盘尺寸大于被移动圆盘时，可将圆盘移至这座塔上。
请你求出将所有圆盘从塔A移动到塔D，所需的最小移动次数是多少。
输入格式
没有输入
输出格式
对于每一个整数n(1≤n≤12),输出一个满足条件的最小移动次数，每个结果占一行。
输入样例：
没有输入
输出样例：
参考输出格式
题目分析与解答
和经典的三柱子汉诺塔问题相比，这里有四个柱子，所以四柱的汉诺塔问题一定是以三柱为基础的。
对于三柱汉诺塔问题，设表示将
个盘子从第一柱移动到第三柱需要的移动次数，则有状态转移方程：
(解释：先把前个盘子移动到第二个柱子用
次，再把最下的圆盘移动到第三个柱子用1次，最后把前
个圆盘移动到第三个柱子。)
基于三柱的汉诺塔，对于四柱汉诺塔问题，设表示将
个盘子从第一柱移动到第四柱需要的移动次数，则有状态转移方程：
(解释：先把前个放在第二个盘子需要
次；剩下的
个在除了第二个盘子的三个盘子上的移动构成三柱汉诺塔问题，将他们移动到第四柱，需要
次；最后将前
个放到第四个盘子需要
次。遍历
取最小值。)
另外，对于三柱汉诺塔问题其实递推方程有数学解：，所以：
动态规划代码：
#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
int main() {
int hanno4[20];
memset(hanno4, 0x3f, sizeof hanno4);
hanno4[0] = 0; hanno4[1] = 1;
for (int i = 2; i <= 12; i++) {
for (int j = 0; j < i; j++) {
// hanno4[i] = min(hanno4[i], hanno4[j] * 2 + (1<<(i-j)) - 1);
hanno4[i] = min(hanno4[i], hanno4[i-j] * 2 + (1<<j) - 1);
}
}
for (int i = 1; i <= 12; i++)
cout << hanno4[i] << endl;
return 0;
}
Northwestern Europe 2002:Euro Efficiency
总时间限制: 1000ms 内存限制: 65536kB
描述
On January 1st 2002, The Netherlands, and several other European countries abandoned their national currency in favour of the Euro. This changed the ease of paying, and not just internationally.
A student buying a 68 guilder book before January 1st could pay for the book with one 50 guilder banknote and two 10 guilder banknotes, receiving two guilders in change. In short:50+10+10-1-1=68. Other ways of paying were: 50+25-5-1-1, or 100-25-5-1-1.Either way, there are always 5 units (banknotes or coins) involved in the payment process, and it
could not be done with less than 5 units.
Buying a 68 Euro book is easier these days: 50+20-2 = 68, so only 3 units are involved.This is no coincidence; in many other cases paying with euros is more efficient than paying with guilders. On average the Euro is more efficient. This has nothing to do, of course, with the value of the Euro, but with the units chosen. The units for guilders used to be: 1, 2.5, 5, 10, 25, 50,whereas the units for the Euro are: 1, 2, 5, 10, 20, 50.
For this problem we restrict ourselves to amounts up to 100 cents. The Euro has coins with values 1, 2, 5, 10, 20, 50 eurocents. In paying an arbitrary amount in the range [1, 100] eurocents, on average 2.96 coins are involved, either as payment or as change. The Euro series is not optimal in this sense. With coins 1, 24, 34, 39, 46, 50 an amount of 68 cents can be paid using two coins.The average number of coins involved in paying an amount in the range [1, 100] is 2.52.
Calculations with the latter series are more complex, however. That is, mental calculations.These calculations could easily be programmed in any mobile phone, which nearly everybody carries around nowadays. Preparing for the future, a committee of the European Central Bank is studying the efficiency of series of coins, to find the most efficient series for amounts up to 100 eurocents. They need your help.
Write a program that, given a series of coins, calculates the average and maximum number of coins needed to pay any amount up to and including 100 cents. You may assume that both parties involved have sufficient numbers of any coin at their disposal.
输入
The first line of the input contains the number of test cases. Each test case is described by 6 different positive integers on a single line: the values of the coins, in ascending order. The first number is always 1. The last number is less than 100.
输出
For each test case the output is a single line containing first the average and then the maximum number of coins involved in paying an amount in the range [1, 100]. These values are separated by a space. As in the example, the average should always contain two digits behind the decimal point. The maximum is always an integer.
样例输入
3
1 2 5 10 20 50
1 24 34 39 46 50
1 2 3 7 19 72
样例输出
2.96 5
2.52 3
2.80 4
题目分析与解答
分析
题目的大意是，给定一组6种不同面值的硬币，每种硬币个数不限，现在你拿着这些硬币去购买价值为total_value的东西，问参与交易的最少硬币个数n是多少(可以多付钱，然后店家找钱)，编程计算当total_value从1到100需要的最少硬币个数求其均值，以及当total_value从1到100中最多需要的硬币个数。
例子
看一个简单的例子，为了例子的直观，现在假设只有三种面值的硬币1,2,10，求total_value从1到10需要的最少硬币个数均值，以及最多需要的硬币个数。
total_value=1时，1张面值为1的硬币就够了，min_count=1。
total_value=2时，1张面值为2的硬币就够了，min_count=1。
total_value=3时，需要1张面值为1的和1张面值为2的，min_count=2。
total_value=4时，需要2张面值为2的，min_count=2。
total_value=5时，需要2张面值为2的和1张面值为1的，min_count=3。
total_value=6时，需要3张面值为2的，min_count=3。
total_value=7时，注意虽然可以3张面值2加1张面值1，这样一共用4张；但是如果1张面值10的给店家，店家找1张面值2的和1张面值1的，交易只用了三张，因此是min_count=3。
total_value=8时，给1张面值10的，找一张面值2的，min_count=2。
total_value=9时，给1张面值10的，找一张面值1的，min_count=2。
total_value=10时，min_count=1。
| total_value | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 |
|---|---|---|---|---|---|---|---|---|---|---|
| min_count | 1 | 1 | 2 | 2 | 3 | 3 | 3 | 2 | 2 | 1 |
于是需要的硬币个数均值：
其中的最大值：
问题的抽象
由上面的分析可以将问题抽象为一个类完全背包问题，用动态规划解决。设硬币面值数组为。定义状态
表示购买价值为
的物品需要参与交易的最少硬币数量。
不过由于存在可以多付钱然后再找钱的过程，背包的容量并不是每次购买的物品的价值，所以memo数组的空间一定要大于100。于是将动态规划分为两个阶段，第一个阶段只考虑付钱而不找钱来计算
，初始
，状态转移方程：
第二个阶段来考虑找钱，比如我们的简单例子中，在第一阶段会求得，用了4个硬币，现在考虑多付钱然后找钱的过程，可以付8找1，付9找2，付10找3，由于店家找钱也是用硬币组合为需要找给买家的价值，所以其实在第一个阶段求解过，于是状态转移方程：
自此问题已经很清晰了，给出动态规划代码：
# include<cstdio>
# include<algorithm>
# include<cmath>
# include<iostream>
using namespace std;
int INF = 0x3f3f3f3f;
const int maxn = 1000; // 不能写100，因为有找钱会减，中间状态可能大于100
int memo[maxn];// memo[k]
int main() {
int n;
// freopen("input.txt", "r", stdin);
cin >> n;//scanf_s("%d", &n);
int coin[10];
for (int i = 0; i < n; i++) {
for (int j = 1; j <= 6; j++)
cin >> coin[j]; //scanf("%d", &coin[j]);
memo[0] = 0; // 初始化
for (int j = 1; j < maxn; j++)
memo[j] = INF;
// 动态规划
for (int j = 1; j <= 6; j++)
for (int k = coin[j]; k <= maxn; k++)
if (memo[k - coin[j]] != INF)
memo[k] = min(memo[k], memo[k - coin[j]] + 1);
for (int j = 1; j <= 6; j++)
for (int k = maxn - coin[j]; k >= 0; k--)
if (memo[k + coin[j]] != INF)
memo[k] = min(memo[k], memo[k + coin[j]] + 1);
int sum = 0, max_count = -1;
for (int j = 1; j <= 100; j++) {
sum += memo[j];
max_count = max(max_count, memo[j]);
}
double ave = (double)sum / 100;
printf("%.2lf %d\n", ave, max_count);
}
// fclose(stdin);
return 0;
}
LeetCode322号题目零钱兑换 - 力扣（LeetCode） 和该题目几乎一样。
(这两个题目的两个for循环可以换位置，不影响求解逻辑)
硬币组合
题目分析与解答
分析
显然的完全背包问题，所以可以对硬币面值做循环，设，则有状态转移方程：
其含义将求解划分为了两个不相交情况的并，如果要求使用使得硬币总量为
的组合数，可以先计算只使用
(即不使用
)使得硬币总量为
的组合数，再加上使用
的组合数(至少使用
一次，所以是
)。
解答
class Solution {
public:
vector<int>coins = {1,5,10,25};
int waysToChange(int n) {
vector<vector<int>>f = vector<vector<int>>(coins.size(), vector<int>(n+1));
for(int k=0;k<=n;k++)f[0][k] = 1;
// for(int i=0; i<coins.length; i++) f[i][0] = 1; // 该语句可以省略，求解逻辑中会包含
for(int i = 1;i < coins.size();i++){
for(int k=0; k <= n; k ++){//
f[i][k] = f[i-1][k];
if(k - coins[i] >= 0)
f[i][k] = (f[i-1][k] + f[i][k-coins[i]]) % 1000000007;
// f[i][k] += f[i][k-coins[i]];
}
}
return f[coins.size()-1][n];
}
};
进一步，如果只关注与求解有关的状态：
class Solution {
public:
int coins[4] = {1, 5,25,10};
int waysToChange(int n) {
vector<int>f(n+1, 0);
f[0] = 1;
for(int c: coins){
for(int i=1; i <= n;i++)
if(i>=c) f[i] = (f[i-c] + f[i]) % 1000000007;
}
return f[n];
}
};
这道题目与上面不同是是指定的，所以不一定可以得到
的数值，上题则是本题的特例。基本求解思路不变，只需要在进行初始化时，注意 f[0][k]，在k不整除coins[0]时置0即可。
class Solution {
public:
int change(int amount, vector<int>& coins) {
if(amount==0) return 1;
if(coins.size()==0) return 0;
vector<vector<int>>f = vector<vector<int>>(coins.size(), vector<int>(amount+1, 0));
// for(int i=0;i<coins.size();i++) f[i][0] = 1; // 该语句可以省略
for(int k=0;k<=amount;k++) f[0][k] = k % coins[0]==0 ? 1:0;
for(int i = 1;i < coins.size();i++){
for(int k=0; k <= amount; k ++){//
f[i][k] = f[i-1][k];
if(k - coins[i] >= 0)
f[i][k] = (f[i-1][k] + f[i][k-coins[i]]);
}
}
return f[coins.size()-1][amount];
}
};
class Solution {
public:
int change(int amount, vector<int>& coins) {
vector<int>f(amount+1, 0);
f[0] = 1;
for(int c: coins){
for(int i=0;i<=amount;i++)
if(i-c>=0)
f[i] += f[i-c];
}
return f[amount];
}
};
(这两个题目的for循环不可以换位置。)
和为 K 的最少斐波那契数字数目
题目分析：根据题意，首先要求得斐波那契数列的一些项，由题目规模的限制，大概求到46项即可。然后问题就转化为一个完全背包问题，使用动态规划。
题目解答：
class Solution {
public:
int fib[51];
void calfib() {
fib[0] = 0; fib[1] = 1;
for (int i = 2; i < 46; i++)
fib[i] = fib[i - 1] + fib[i - 2];
}
int findMinFibonacciNumbers(int k) {
int res = 0, pos = 45;
calfib();
while (k) {
for (int i = pos; i >= 1; i--) {
if (fib[i] <= k) {
k -= fib[i];
res++;
pos = i;
break;
}
}
}
return res;
}
};
跳跃游戏
题目分析：根据题意，对于给定的数组，
的值表示处在位置
能跳跃的最大距离，设
于是有状态转移方程：
其中之前的必然已经被求解过，故可优化到：
题目解答：
class Solution {
public:
// memo[i+1] = (j<=memo[i])max(j+nums[j], memo[i] + nums[memo[i]])
vector<int>memo;
int jump(vector<int>& nums) {
if(nums.size()<=1)return 0;
memo = vector<int>(nums.size()+1, 0);
memo[0] = 0;
int cur=0;
for(int i=0;i<nums.size();i++){
for(int j=cur;j<=memo[i];j++)
memo[i+1] = max(j+nums[j],memo[i+1]);
cur = memo[i];
if(memo[i+1] >= nums.size()-1) return i+1;
}
return memo[0];
}
};
