C語言數學問題與簡單DP01揹包問題詳解

2022-04-12 13:00:24

數學

顧名思義，數學類的題就是都可以用數學知識求解。

買不到的數目

這是第四屆藍橋杯省賽C++A組,第四屆藍橋杯省賽JAVAC組的一道題

小明開了一家糖果店。

他別出心裁：把水果糖包成4顆一包和7顆一包的兩種。

糖果不能拆包賣。

小朋友來買糖的時候，他就用這兩種包裝來組合。

當然有些糖果數目是無法組合出來的，比如要買 10 顆糖。

你可以用計算機測試一下，在這種包裝情況下，最大不能買到的數量是17。

大於17的任何數位都可以用4和7組合出來。

本題的要求就是在已知兩個包裝的數量時，求最大不能組合出的數位。

輸入格式
兩個正整數 n,m，表示每種包裝中糖的顆數。

輸出格式
一個正整數，表示最大不能買到的糖數。

資料範圍
2≤n,m≤1000，
保證資料一定有解。

輸入樣例：

4 7

輸出樣例：

17

這道題簡單看一下，似乎沒有什麼規律，我們可以先打表來找一下規律：

#include <bits/stdc++.h>

using namespace std;

//給定一個m，是否能用p和q湊出來
bool dfs(int m,int p,int q)
{
    if(m == 0) return true;

    if(m >= p && dfs(m - p,p,q)) return true;
    if(m >= q && dfs(m - q,p,q)) return true;

    return false;
}

int main()
{
    int p,q;
    cin >> p >> q;
    int res = 0;
    for(int i = 1; i <= 1000;i ++)
    {
        if(!dfs(i,p,q)) res = i;
    }

    cout << res << endl;

    return 0;
}

打表暴力搜尋找規律

2 3 輸出 1
3 5 輸出7
3 7 輸出11
3 10 輸出17
...
最後得到規律
如果 a,b均是正整數且互質，那麼由 ax+by,x≥0,y≥0ax+by,x≥0,y≥0 不能湊出的最大數是 (a−1)(b−1)−1。

接下來再看數學程式碼：

#include <bits/stdc++.h>

using namespace std;

int main()
{
    int p, q;
    cin >> p >> q;
    cout << (p - 1) * (q - 1) - 1 << endl;

    return 0;
}

螞蟻感冒

這也是藍橋杯的一道題，來源：第五屆藍橋杯省賽C++A/B組

長 100 釐米的細長直杆子上有 n 只螞蟻。

它們的頭有的朝左，有的朝右。

每隻螞蟻都只能沿著杆子向前爬，速度是 1 釐米/秒。

當兩隻螞蟻碰面時，它們會同時掉頭往相反的方向爬行。

這些螞蟻中，有 1 只螞蟻感冒了。

並且在和其它螞蟻碰面時，會把感冒傳染給碰到的螞蟻。

請你計算，當所有螞蟻都爬離杆子時，有多少隻螞蟻患上了感冒。

輸入格式
第一行輸入一個整數 n, 表示螞蟻的總數。

接著的一行是 n 個用空格分開的整數 Xi, Xi 的絕對值表示螞蟻離開杆子左邊端點的距離。

正值表示頭朝右，負值表示頭朝左，資料中不會出現 0 值，也不會出現兩隻螞蟻佔用同一位置。

其中，第一個資料代表的螞蟻感冒了。

輸出格式
輸出1個整數，表示最後感冒螞蟻的數目。

資料範圍
1<n<50,
0<|Xi|<100

輸入樣例1：

3
5 -2 8

輸出樣例1：

1

輸入樣例2：

5
-10 8 -20 12 25

輸出樣例2：

3

這題很有意思，唯讀題就會有這種想法，如果一隻螞蟻從左往右走，另外一隻從右往左走，有一隻感冒了，那麼，他們相遇後就會分別向相反的方向走。

按照這個思路，我們來寫一個暴力解法：

#include <bits/stdc++.h>

using namespace std;

const int N = 1e5 + 10;

int n, pos;
int a[N];
int ans = 1;
int cmp(int a, int b)
{
  return abs(a) < abs(b);
}
int main()
{
  cin >> n;
  for (int i = 0; i < n; i++)
    cin >> a[i];
  int pre = a[0];
  sort(a, a + n, cmp); //先按絕對值 將螞蟻的位置排好
  for (int i = 0; i < n; i++)
  {
    if (a[i] == pre)
      pos = i;
  }
  int flag = 0;
  if (pre > 0) //首先感染的螞蟻向右走
  {
    for (int i = pos + 1; i < n; i++)
    {
      if (a[i] > 0)
        continue;
      if (a[i] < 0)
      {
        ans++;
        flag = 1; //標記右面有螞蟻向左走
      }
    }
    for (int i = pos - 1; i >= 0; i--)
    {
      if (flag) //在右邊有往左走的螞蟻前提下
      {
        if (a[i] > 0) //如果左面有向右走的那麼肯定會傳染
          ans++;
      }
    }
  }
  if (pre < 0)  //首先感染的螞蟻向左走，方法同上
  {
    for (int i = pos - 1; i >= 0; i--)
    {
      if (a[i] < 0)
        continue;
      if (a[i] > 0)
      {
        ans++;
        flag = 1;
      }
    }
    for (int i = pos + 1; i < n; i++)
    {
      if (a[i] > 0)
        continue;
      if (flag)
      {
        if (a[i] < 0)
          ans++;
      }
    }
  }
  cout << ans << endl;

  return 0;
}

但這中間就有一個很有意思的地方就是左邊的往右走，右邊的往左走，有一隻感冒了，它們相遇後還是等價於有兩隻螞蟻分別往前走，只是這樣兩隻螞蟻都感冒了，這樣之後遇到的螞蟻也會被感冒，這樣想就不會有掉頭做判斷這一步了，接下來請看程式碼：

#include <bits/stdc++.h>

using namespace std;

const int N = 55;

int n;
int x[N];

int main()
{
    cin >> n;
    for (int i = 0; i < n; i ++ ) cin >> x[i];

    int left = 0, right = 0;    // 分別表示左邊向右走的螞蟻數量，和右邊向左走的螞蟻數量
    for (int i = 1; i < n; i ++ )
        if (abs(x[i]) < abs(x[0]) && x[i] > 0) left ++ ;
        else if (abs(x[i]) > abs(x[0]) && x[i] < 0) right ++ ;

    if (x[0] > 0 && right == 0 || x[0] < 0 && left == 0) cout << 1 << endl;
    else cout << left + right + 1 << endl;

    return 0;
}

飲料換購

來源：第六屆藍橋杯省賽C++A/C組,第六屆藍橋杯省賽JAVAB組

樂羊羊飲料廠正在舉辦一次促銷優惠活動。樂羊羊C型飲料，憑3個瓶蓋可以再換一瓶C型飲料，並且可以一直迴圈下去(但不允許暫借或賒賬)。

請你計算一下，如果小明不浪費瓶蓋，儘量地參加活動，那麼，對於他初始買入的 n 瓶飲料，最後他一共能喝到多少瓶飲料。

輸入格式
輸入一個整數 n,表示初始買入的飲料數量。

輸出格式
輸出一個整數，表示一共能夠喝到的飲料數量。

資料範圍
0<n<10000

輸入樣例：

100

輸出樣例：

149

這題就很簡單了,還是先看模擬程式碼：

#include <bits/stdc++.h>

using namespace std;

int main()
{
    int n;
    cin >> n;

    int res = n;
    while (n >= 3)
    {
        res += n / 3;
        n = n / 3 + n % 3;
    }

    cout << res << endl;

    return 0;
}

然後是數學公式程式碼：

#include <bits/stdc++.h>

using namespace std;

int main()
{
    int n;
    cin >> n;
    cout << n + (n - 1) / 2 << endl;
    return 0;
}

簡單DP

先來看題：01揹包問題是非常經典的DP問題。

01揹包問題

有 N 件物品和一個容量是 V 的揹包。每件物品只能使用一次。

第 i 件物品的體積是 vi，價值是 wi。

求解將哪些物品裝入揹包，可使這些物品的總體積不超過揹包容量，且總價值最大。
輸出最大價值。

輸入格式
第一行兩個整數，N，V，用空格隔開，分別表示物品數量和揹包容積。

接下來有 N 行，每行兩個整數 vi,wi，用空格隔開，分別表示第 i 件物品的體積和價值。

輸出格式
輸出一個整數，表示最大價值。

資料範圍
0<N,V≤1000
0<vi,wi≤1000

輸入樣例

4 5
1 2
2 4
3 4
4 5

輸出樣例：

8

題目介紹

有 N 件物品和一個容量為 V的揹包，每件物品有各自的價值且只能被選擇一次，要求在有限的揹包容量下，裝入的物品總價值最大。

「0-1 揹包」是較為簡單的動態規劃問題，也是其餘揹包問題的基礎。

動態規劃是不斷決策求最優解的過程，「0-1 揹包」即是不斷對第 i個物品的做出決策，「0-1」正好代表不選與選兩種決定

二維

（1）狀態f[i][j]定義：前 i個物品，揹包容量 j 下的最優解（最大價值）：

當前的狀態依賴於之前的狀態，可以理解為從初始狀態f[0][0] = 0開始決策，有 N 件物品，則需要 N 次決策,每一次對第 i 件物品的決策，狀態f[i][j]不斷由之前的狀態更新而來。
（2）當前揹包容量不夠（j < v[i]），沒得選，因此前 i個物品最優解即為前 i−1個物品最優解：

對應程式碼：f[i][j] = f[i - 1][j]。
（3）當前揹包容量夠，可以選，因此需要決策選與不選第 i 個物品：

選：f[i][j] = f[i - 1][j - v[i]] + w[i]。
不選：f[i][j] = f[i - 1][j] 。

我們的決策是如何取到最大價值，因此以上兩種情況取 max() 。

接下來請看二維求解程式碼：

#include<bits/stdc++.h>

using namespace std;

const int MAXN = 1005;
int v[MAXN];    // 體積
int w[MAXN];    // 價值 
int f[MAXN][MAXN];  // f[i][j], j體積下前i個物品的最大價值 

int main() 
{
    int n, m;   
    cin >> n >> m;
    for(int i = 1; i <= n; i++) 
        cin >> v[i] >> w[i];

    for(int i = 1; i <= n; i++) 
        for(int j = 1; j <= m; j++)
        {
            //  當前揹包容量裝不進第i個物品，則價值等於前i-1個物品
            if(j < v[i]) 
                f[i][j] = f[i - 1][j];
            // 能裝，需進行決策是否選擇第i個物品
            else    
                f[i][j] = max(f[i - 1][j], f[i - 1][j - v[i]] + w[i]);
        }           

    cout << f[n][m] << endl;

    return 0;
}

一維

將狀態f[i][j]優化到一維f[j]，實際上只需要做一個等價變形。

原式：f[i][j] = max(f[i-1][j], f[i - 1][j - v[i]] + w[i]);

改成一維：f[j] = max(f[j], f[j - v[i]] + w[i]);

先來看程式碼：

#include<bits/stdc++.h>

using namespace std;

const int N = 1010;

int f[N];
int v[N], w[N];
int n, m;
int main()
{
    

    cin >> n >> m;
    for (int i = 1; i <= n; i ++ ) cin >> v[i] >> w[i];

    for (int i = 1; i <= n; i++) {
        for (int j = m; j >= v[i]; j--) 
        {
            f[j] = max(f[j], f[j - v[i]] + w[i]);
        }
    }

    cout << f[m] << endl;
}

這中間有一個點大家可能不太好理解，為什麼是for (int j = m; j >= v[i]; j--)，而不是for (int j = v[i]; j <= m; j++)

首先我們先來模擬一下如果是for (int j = v[i]; j <= m; j++)，迴圈就是：

for (int i = 1; i <= n; i++) {
        for (int j = v[i]; j <= m; j++) {
            f[j] = max(f[j], f[j - v[i]] + w[i]);
        }
    }

來看題

輸入樣例

4 5
1 2
2 4
3 4
4 5
物品體積價值
i=1 1 2
i=2 2 4
i=3 3 4
i=4 4 5

當還沒進迴圈的時候

f[0] = 0; f[1] = 0; f[2] = 0; f[3] = 0; f[4] = 0; f[5] = 0;

當進入迴圈 i == 1 時：v[i]=1,w[i]=2;

j=1:f[1]=max(f[1],f[1-1]+2),即max(0,2)=2;即f[1]=2;
j=2:f[2]=max(f[2],f[2-1]+2),即max(0,4)=4;即f[2]=4;
j=3:f[3]=max(f[3],f[3-1]+2),即max(0,6)=6;即f[3]=6;
j=4:f[4]=max(f[4],f[4-1]+2),即max(0,8)=8;即f[4]=8;
j=5:f[5]=max(f[5],f[5-1]+2),即max(0,10)=10;即f[5]=10;

當到這裡的時候就已經出問題了。

//如果 j 層迴圈是逆序的： for (int i = 1; i <= n; i++) {<!--{C}%3C!%2D%2D%20%2D%2D%3E--> for (int j = m; j >= v[i]; j--) {<!--{C}%3C!%2D%2D%20%2D%2D%3E--> f[j] = max(f[j], f[j - v[i]] + w[i]); } }//如果 j 層迴圈是逆序的：
    for (int i = 1; i <= n; i++) {
        for (int j = m; j >= v[i]; j--) {
            f[j] = max(f[j], f[j - v[i]] + w[i]);
        }
    }

輸入樣例

   4 5
   1 2
   2 4
   3 4
   4 5
   物品體積價值
   i=1 1       2
   i=2 2       4
   i=3 3       4
   i=4 4       5

   當還沒進迴圈的時候
   f[0] = 0; f[1] = 0; f[2] = 0; f[3] = 0; f[4] = 0; f[5] = 0;
   當進入迴圈時i==1，w[i]=2,v[i]=1;
   j=5:f[5]=max(f[5],f[5-1]+2),即max(0,2)=2;即f[5]=2;
   j=4:f[4]=max(f[4],f[4-1]+2),即max(0,2)=2;即f[4]=2;
   j=3:f[3]=max(f[3],f[3-1]+2),即max(0,2)=2;即f[3]=2;
   j=2:f[2]=max(f[2],f[2-1]+2),即max(0,2)=2;即f[2]=2;
   j=1:f[1]=max(f[1],f[1-1]+2),即max(0,2)=2;即f[1]=2;
   當進入迴圈 i == 2 時,w[i]=4,v[i]=2;
   j=5:f[5]=max(f[5],f[5-2]+4),即max(2,6)=6,即f[5]=6;
   j=4:f[5]=max(f[4],f[4-2]+4),即max(2,6)=6,即f[4]=6;
   j=3:f[5]=max(f[3],f[3-2]+4),即max(2,6)=6,即f[3]=6;
   j=2:f[5]=max(f[2],f[2-2]+4),即max(2,4)=4,即f[2]=4;
   當進入迴圈 i == 3 時: w[i] = 4; v[i] = 3;
   j=5:f[5]=max(f[5],f[5-3]+4),即max(6,8)=8,即f[5]=8;
   j=4:f[4]=max(f[4],f[4-3]+4),即max(6,6)=6,即f[4]=6;
   j=3:f[3]=max(f[3],f[3-3]+4),即max(6,4)=6,即f[3]=6;
   當進入迴圈 i == 3 時: w[i] = 5; v[i] = 4;
   j=5:f[5]=max(f[5],f[5-4]+5),即max(8,7)=8,即f[5]=8;
   j=4:f[4]=max(f[4],f[4-4]+5),即max(6,5)=6,即f[4]=6;