# 北軟100 pB 百貨公司選購促銷商品的最佳組合(Hard Solution)
###### tags: `北軟100`

## 題目

某百貨公司推出福箱活動 ：某百貨公司推出福箱活動，每人可購買一個福箱來裝這次活動特價區的限 人可購買一個福箱來裝這次活動特價區的限量商品，每件商品不限制購買數量 ，每件商品不限制購買數量，但總重量不得超過 ，但總重量不得超過 50KG（箱體重量不計）。

某位精打細算的媽媽想利用這次的活動來選購最值錢的商品，在不超重的狀況下 ，在不超重的狀況下
（商品總重量小於等於 （商品總重量小於等於 50KG），請問這位媽媽應該如何去選取最值錢的商品組
合?請將最佳組合的商品細目列出 請將最佳組合的商品細目列出。

特價區商品如下：


執行範例：


評分：

1. 程式介面(5 分)
2. 程式執行正確性(20 分)

## 想法

這題用到一個很著名的演算法，名為[0/1 Knapsack Problem](http://www.csie.ntnu.edu.tw/~u91029/KnapsackProblem.html#3)。

我們可以用dynamic programming來解決這個問題。
用一個名為dp的array儲存「當限制重量為W時，能夠湊成不超過限制重量的最大利益」。

而當我們決定於某個重量W時，我們可以考慮，有一物品i的重量為weight[i]，在重量為W-weight[i]時，某個物品新增上去時的利益是否比當前的重量W還要大。
如果還要大，就更新dp[W]的值，如果更小，那就不變更。

根據上面的考慮，我們就能導出轉移式：$max(dp[j],dp[j-weight[i]]+price[i])$
其中weight為物品i的重量，price為某個物品i的價值。

印出來的方式我們可以使用回朔法。
開一個二維陣列紀錄物品i在重量為j的時候是否有放進去，
而有沒有放進去的根據為「是否更新了當前最大的價值」。

而回朔的方式為欲求當前重量W是否放進某個物品i，則price[i,W]會等於true，代表最大利益在重量等於W時，內部存在一個物品i。

接下來我們從W減去物品i的重量，繼續執行回朔。

而由於dp[W] = dp[W-weight[i]] + price[i]
所以dp[W-weight[i]] + price[i] = dp[W]。

因此，這樣找下來一定可以回朔出背包內的物品。

更詳細的說明你可以參考上面的連結。

## 程式碼(C#)

using System;
using System.Collections.Generic;
using System.ComponentModel;
using System.Data;
using System.Drawing;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
using System.Windows.Forms;

namespace problemB
{
    public partial class Form1 : Form
    {
        public Form1()
        {
            InitializeComponent();
        }

        private void button1_Click(object sender, EventArgs e)
        {
            int[] priceArray = new int[6];
            int[] weightArray = new int[6];
            string[] itemName = new string[6];

            int weightLimit = Convert.ToInt32(textBox19.Text);

            int[] dp = new int[weightLimit + 1];
            bool[,] place = new bool[7, weightLimit + 1];

            for(int i = 0; i < itemName.Length; i++)
            {
                itemName[i] = this.Controls["textBox" + (1 + i)].Text;
            }
            for (int i = 0; i < priceArray.Length; i++)
            {
                priceArray[i] = Convert.ToInt32(this.Controls["textBox" + (7 + i)].Text);
            }
            for (int i = 0; i < priceArray.Length; i++)
            {
                weightArray[i] = Convert.ToInt32(this.Controls["textBox" + (13 + i)].Text);
            }
            for (int i = 0; i < priceArray.Length; i++)
            {
                for (int j = weightArray[i]; j <= weightLimit; j++)
                {
                    if (dp[j] < dp[j - weightArray[i]] + priceArray[i])
                    {
                        dp[j] = Math.Max(dp[j], dp[j - weightArray[i]] + priceArray[i]);
                        place[i, j] = true;
                    }
                }
            };
            List<string> list = new List<string>();
            for (int i = 5, j = weightLimit; i >= 0; i--)
            {
                if (place[i, j] == true)
                {
                    list.Add(itemName[i]);
                    j -= weightArray[i];
                }
            }
            label6.Text = String.Join("+", list);
            label8.Text = "=" + dp[weightLimit];
        }
    }
}