[紅利贈品最滿意] 某公司週年慶推出贈品酬謝顧客，顧客可使用收集的紅利點數來
兌換贈品，美美希望能夠使用她所累積的紅利點數（假設為 r 點），兌換到最滿意
的贈品組合，請幫她計算：她的全部紅利點數，所能兌換的贈品最大滿意值總和是
多少呢? 下表中列出這家公司所準備的 5 種贈品和兌換所需之紅利點數，以及美美
對於各贈品的滿意值，但因贈品數量有限，兌換完畢即不再補充。
兌換時，假設贈品之滿意總值可以直接將其加總，同一種贈品的兌換數量可超
過一個，但須小於當時該贈品之剩餘數量，最後無法再行兌換的紅利點數可以剩下。
舉例來說，若美美有紅利點數 40 點，贈品 A,B,C,D,E 的剩餘數量分別為 10, 10, 1, 2, 0 個，
則美美可兌換贈品的最大滿意值總和為 160。

贈品名稱贈品滿意值兌換所需紅利點數
A
B
C
D
E
100
75
45
20
3
30
18
10
5
1

輸入/輸出說明：請在表單上建立 2 個 LABEL、7 個 TEXTBOX 及 1 個按鈕，其中第 1
個 LABEL 表示「輸入紅利點數 r」，對應第 1 個 TEXTBOX 可輸入一個正整數；第 2
個 LABEL 表示「分別輸入贈品 A,B,C,D,E 的剩餘數量」，第 2~6 個 TEXTBOX 分別輸
入 5 個正整數 (可包含 0)。按下按鈕，於第 7 個 TEXTBOX 輸出兌換的贈品最大滿意
值總和。
程式執行順序：輸入紅利點數 r，輸入贈品 A,B,C,D,E 的剩餘數量，按下按鈕，輸出。


此題類似背包問題，可以先看看之前我的一些論述。
背包問題

演算法：
    

家豪版

Youtube 暴力法教學影片

cpp 程式
#include <iostream>
#include <math.h> using namespace std;
int main() {
     int x;
     int Max,a,b,c,d,e,s,N;
     int a1,b1,c1,d1,e1;//目前可使用的產品數
     int a2,b2,c2,d2,e2;
     N=40;//40點
     Max = 0;//目前最大滿意值
     a1=min(10,N/30);//A產品需要 30 點，N/30=1，只能換 1 個
     b1=min(10,N/18);//B產品需要 18 點，N/18=2，只能換 2 個
     c1=min(1,N/10);//C產品需要 10 點，N/10=4，但產品數為 1，所以只能換 1 個
     d1=min(2,N/5);//D產品需要 5 點，N/5=8，但產品數為 2，所以只能換 2 個
     e1=min(0,N/1);//E產品需要 1 點，N/1=40，但產品數為 0，所以只能換 0 個
     for(a=0;a<=a1;a++)
          for(b=0;b<=b1;b++)
               for(c=0;c<=c1;c++)
                    for(d=0;d<=d1;d++)
                         for(e=0;e<=e1;e++){
                              s = a*30 + b*18 + c*10 + d*5 + e*1;//消耗的點數
                              if(s<=N){//消耗點數小於等於 N 才可以
                                   x = a*100 + b*75 + c*45 + d*20 + e*3;//滿意值
                                   if(x>Max){
                                        Max = x;
                                        a2=a;b2=b;c2=c;d2=d;e2=e;//紀錄最大值發生時的產品數
                                   }
                              }
                         }
     cout << "A=" << a2 << ",B=" << b2 << ",C=" << c2 << ",D=" << d2 << ",E=" << e2 << ", 最大值=" << Max << endl;      return 0;
}


動態規劃法

Youtube 教學影片

主程式(紅色區)，
換物遞迴副程式 P_to_S(目前換到的總喜悅值, 開始兌換起始編號, 可用點數) (藍色區)

遞迴版
Private Sub Button1_Click(sender As Object, e As EventArgs) Handles Button1.Click
    Dim i As Integer
    init()
    uP = 0 : Cmax = 0
    freePoin = TextBox7.Text "可用點數
    TextBox6.Text = P_to_S(0, 0, freePoin) "得到最大值
    For i = 0 To bestP "show 出買的物品
        TextBox6.Text = nameP(best(i, 0)) & "*" & best(i, 1) & If(i = 0, " = ", " , ") & TextBox6.Text
    Next
End Sub


"遞迴找滿意度, 傳入 : 目前分配總值 total, 從第幾項物品開始計算 n, 剩餘可用點數 fp, 傳回 : 最好的滿意度
Function P_to_S(ByVal total As Integer, ByVal star As Integer, ByVal fp As Integer) As Integer

Dim a As Integer, b As Integer, i As Integer, c As Integer, max As Integer
    If ((star >= NN) Or (fp <= 0)) Then Return (0)
    For i = star To NN - 1
        a = Math.Min(fp \ Points(i), Surplus(i))
        Do While a > 0
            b = fp - Points(i) * a "剩餘點數
            c = Satisfaction(i) * a "得到的喜悅度
            unit(uP, 0) = i : unit(uP, 1) = a : uP += 1 "紀錄換的物品
            If (b > 0) Then "還有餘點, 可以再分配其他
                c += P_to_S(total + c, i + 1, b)
            End If
            If (c > max) Then max = c
            If (total + c > Cmax) Then
                copyArray()
                Cmax = total + c
            End If
            a -= 1
            uP -= 1
        Loop
    Next
    Return (max)
End Function

"將目前最好的情況記錄在 best 陣列
Sub copyArray()
Dim i As Integer
For i = 0 To uP - 1
    best(i, 0) = unit(i, 0) : best(i, 1) = unit(i, 1) "(註標 0 是物品編號 , 註標 1 是物品數量
Next
bestP = uP - 1
End Sub

Sub init()
Satisfaction(0) = Val(TextBox8.Text) : Points(0) = Val(TextBox13.Text) : Surplus(0) = Val(TextBox1.Text)
Satisfaction(1) = Val(TextBox9.Text) : Points(1) = Val(TextBox14.Text) : Surplus(1) = Val(TextBox2.Text)
Satisfaction(2) = Val(TextBox10.Text) : Points(2) = Val(TextBox15.Text) : Surplus(2) = Val(TextBox3.Text)
Satisfaction(3) = Val(TextBox11.Text) : Points(3) = Val(TextBox16.Text) : Surplus(3) = Val(TextBox4.Text)
Satisfaction(4) = Val(TextBox12.Text) : Points(4) = Val(TextBox17.Text) : Surplus(4) = Val(TextBox5.Text)
End Sub



昊朋版

黃翰版

此版是用暴力法，但程式也不簡潔，既然都暴力法了，就不用存那麼多變數。
簡單明潦列舉，並記住最大就好。


Dim arr(100) As Integer, current As Integer = 0
Private Sub Button1_Click(sender As Object, e As EventArgs) Handles Button1.Click

Dim r As Integer = Val(TextBox1.Text)
Dim a As Integer = Val(TextBox2.Text)
Dim b As Integer = Val(TextBox3.Text)
Dim c As Integer = Val(TextBox4.Text)
Dim d As Integer = Val(TextBox5.Text)
Dim e2 As Integer = Val(TextBox6.Text)
Dim i1, i2, i3, i4, i5 As Integer
Dim price, price_max, cost As Integer
price_max = 0
For i1 = 0 To a
    price = 0
    cost = r
    If cost > 30 * i1 Then
        cost -= 30 * i1
        price += 100 * i1
    End If
    For i2 = 0 To b
        Call push(cost)
        Call push(price)
        If cost > 18 * i2 Then
            cost -= 18 * i2
            price += 75 * i2
        End If
        For i3 = 0 To c
            Call push(cost)
            Call push(price)
            If cost > 10 * i3 Then
                cost -= 10 * i3
                price += 45 * i3
            End If
            For i4 = 0 To d
                Call push(cost)
                Call push(price)
                If cost > 5 * i4 Then
                    cost -= 5 * i4
                    price += 20 * i4
                End If
                For i5 = 0 To e2
                    Call push(cost)
                    Call push(price)
                    If cost > i5 Then
                        cost -= i5
                        price += 3 * i5
                        If price > price_max Then
                            price_max = price
                        End If
                    End If
                    price = pop()
                    cost = pop()
                Next
                price = pop()
                cost = pop()
            Next
            price = pop()
            cost = pop()
        Next
        price = pop()
        cost = pop()
    Next
Next
TextBox7.Text = price_max
End Sub

Public Sub push(ByVal n As Integer)
If current <= 100 Then
    arr(current) = n
    current += 1
End If
End Sub

Function pop() As Integer
If current >= 0 Then
    current -= 1
    Return arr(current)
End If
End Function