這是一個動態規劃題，據說是背包問題的變形。我動態規劃做得很少，解法一直按照算法導論的思想分解重疊子問題。
題意是用錢盡可能多的買物品，每種物品買一個，問有多少種買法。
我也想不出這是什麼背包問題的變形，沒做過幾個背包問題，也沒看過背包九講。還是堅持認為正確的用狀態描述成子問題
就一定能解題的。今天和隊友在做專題時候做到這個題，我一直做了一上午都沒出來。
後面發現了個性質就可以直接轉換為類似最簡單的背包問題了。排序物品價值，從最大物品開始分解子問題，用剩余物品數
和錢描述問題的狀態。當前物品是否必須取，是根據當前的錢把剩下的物品全買了之後剩下的錢還是否大於當前物品的價值，
如果大於就必須買，否則可以買或者不買。
為了正確描述問題的狀態，必須事先排序價值數組，因為排序之後可以保證不能買當前物品的時候一定不能買前面的物品，
那麼我們對前面物品的處理就是正確的了。至此可以進行最簡單的子問題分解了。到最後物品處理完之後（物品數為0），如果錢
一點都沒減少，那麼(0, M) = 0，否則(0, M) = 1。注意這個邊界處理，否則會wa。
所以，需要先對價值數組排序，並計算出表示前N個物品價值和的數組。
做不出來的時候，翻了下別人的解法，一頭霧水。看來還是算法導論的思想指導意義大多了。。。
代碼如下：
#include <stdio.h>
#include <string.h>
#include <algorithm>
using namespace std;
typedef long long INT;
INT nAns[40][1010];
INT nValue[100];
INT nSum[100];
INT nN, nM;
INT GetAns(INT nNum, INT nMoney)
{
if (nAns[nNum][nMoney] == -1)
{
if (nNum == 0)
{
nAns[nNum][nMoney] = 1;
if (nMoney == nM)
{
nAns[nNum][nMoney] = 0;
}
}
else
{
INT nRet = 0;
if (nMoney - nSum[nNum - 1] >= nValue[nNum])
{
nRet = GetAns(nNum - 1, nMoney - nValue[nNum]);
}
else
{
if (nMoney >= nValue[nNum])
{
nRet += GetAns(nNum - 1, nMoney - nValue[nNum]);
}
nRet += GetAns(nNum - 1, nMoney);
}
nAns[nNum][nMoney] = nRet;
}
}
return nAns[nNum][nMoney];
}
int main()
{
INT nT;
scanf("%I64d", &nT);
for (INT i = 1; i <= nT; ++i)
{
scanf("%I64d%I64d", &nN, &nM);
for (INT j = 1; j <= nN; ++j)
{
scanf("%I64d", &nValue[j]);
}
memset(nAns, -1, sizeof(nAns));
sort(nValue + 1, nValue + nN + 1);
nSum[0] = 0;
for (INT j = 1; j <= nN; ++j)
{
nSum[j] = nSum[j - 1] + nValue[j];
}
printf("%I64d %I64d\n", i, GetAns(nN, nM));
}
return 0;
}
