题目描述
书有4种，每种价格不同，每本书可以无限买，问刚好花m块钱的方案数？
| f1-完全背包 |
基本分析
- 完全背包裸题
代码
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int MAX_M = 1000;
int f[MAX_M + 10];
int v[5] = {0, 10, 20, 50, 100};
int m;
int main()
{
scanf("%d", &m);
f[0] = 1;
for (int i = 1; i <= 4; i ++)
{
for (int j = v[i]; j <= m; j ++)
f[j] += f[j - v[i]];
}
printf("%d\n", f[m]);
return 0;
}
总结
- 朴素定义？f[i][j]表示买前i本书，价格恰好为j的方案数
- 空间优化？第二维度正序遍历