題目大概:
用n元買書,書有10 20 50 100元的。問有多少種買書方案。
思路:
這個題是完全背包問題的方案數問題,即每一樣物品是可以無限制的拿取的。
狀态h[i]是i元的方案數,這個題和數字組合非常相似。把完全背包問題變換一下就可以了。
即把完全背包的兩層循環裡的max(h[i],h[i-a[j]])改成h[i]+h[i-a[j]]。
感想:
無。
代碼:
已整理
#include <iostream>
using namespace std;
int main()
{
int n;
int a[5]= {0,10,20,50,100},h[1001]= {0};
h[0]=1;
cin>>n;
for(int i=1; i<=4; i++)
for(int j=a[i]; j<=n; j++)
{
h[j]+=h[j-a[i]];
}
cout<<h[n];
return 0;
}