#include<iostream>
#include<cstdio>
using namespace std;
int main()
{ //f:least num
int i, m, n, p[1005], f[1005]={};
scanf("%d%d", &m, &n);
for(int i=1; i<=m; i++)
scanf("%d", &p[i]);
for(i=1; f[i-1]<=n; i++)
{
f[i]=0xfffffff;
for(int j=1; j<=m; j++)
if(i>=p[j]) f[i]=min(f[i], f[i-p[j]]+1);
}
printf("%d", i-2);
}
#123 滚动数组の完全背包
2018-03-22 17:49:23 By lris
评论
lris
啊对,这个dp数组开太小了,要大一点
- 2018-03-22 17:54:04
NaCl
关于 f[i] = std::min(f[i], f[i-p[j]]+1)
如前述,此过程是寻找最小需求量.
p 数组存放所有面值.
内层循环中,每次我们先取一张 p[j] 元邮票(前提是 p[j] 不大于总金额).
要表示 i 元还差 i-p[j] 元,而 i-p[j] 元最小需求量 f[i-p[j]] 已经求出. 这里 +1 不会损失最优解,因为新取的 p[j] 元也占据某个空间——即使它需求量不一定最小.
通过内层循环得到最小的 f[i] 值.
开始时 f[i] 赋为 0xfffffff,是迁就后面的 std::min(f[i], f[i-p[j]]+1).
0:34,某翎闪了,告辞
- 2018-03-24 00:35:11
发表评论
可以用@mike来提到mike这个用户,mike会被高亮显示。如果你真的想打“@”这个字符,请用“@@”。