UOJ Logo lris的博客

博客

#123 滚动数组の完全背包

2018-03-22 17:49:23 By lris
#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);
}

不会解释qwq,书里有讲(请翻到紫书||一本通dp那节)

评论

lris
啊对,这个dp数组开太小了,要大一点
NaCl
某翎强行解释 ing… for(i=1; f[i-1] <= n; i++){ // f 数组意思是需求量最少的邮票的需求量 // 外层循环完成动态规划 // 跳出循环时,f[i-2] 为 f 数组内最后一个 <=n 的数,故 i-2 为答案 f[i]=0xfffffff; for(int j=1; j<=m; j++) if(i >= p[j]) // 如果总价 3 元,当然不需要 5 元的邮票 f[i] = std::min(f[i], f[i-p[j]]+1); // 通过内层循环找到“最少”的需求量 }
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,某翎闪了,告辞

发表评论

可以用@mike来提到mike这个用户,mike会被高亮显示。如果你真的想打“@”这个字符,请用“@@”。