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