這是一個動態(tài)規(guī)劃題，據(jù)說是背包問題的變形。我動態(tài)規(guī)劃做得很少，解法一直按照算法導論的思想分解重疊子問題。
題意是用錢盡可能多的買物品，每種物品買一個，問有多少種買法。
我也想不出這是什么背包問題的變形，沒做過幾個背包問題，也沒看過背包九講。還是堅持認為正確的用狀態(tài)描述成子問題
就一定能解題的。今天和隊友在做專題時候做到這個題，我一直做了一上午都沒出來。
后面發(fā)現(xiàn)了個性質就可以直接轉換為類似最簡單的背包問題了。排序物品價值，從最大物品開始分解子問題，用剩余物品數(shù)
和錢描述問題的狀態(tài)。
當前物品是否必須取，是根據(jù)當前的錢把剩下的物品全買了之后剩下的錢還是否大于當前物品的價值，
如果大于就必須買，否則可以買或者不買。 為了正確描述問題的狀態(tài)，必須事先排序價值數(shù)組，因為排序之后可以保證不能買當前物品的時候一定不能買前面的物品，
那么我們對前面物品的處理就是正確的了。至此可以進行最簡單的子問題分解了。到最后物品處理完之后（物品數(shù)為0），如果錢
一點都沒減少，那么(0, M) = 0，否則(0, M) = 1。注意這個邊界處理，否則會wa。
所以，需要先對價值數(shù)組排序，并計算出表示前N個物品價值和的數(shù)組。
做不出來的時候，翻了下別人的解法，一頭霧水。看來還是算法導論的思想指導意義大多了。。。
代碼如下：
#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;
}