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那节）

#123

lris

啊对，这个dp数组开太小了，要大一点

2018-03-22 17:54:04
回复

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); // 通过内层循环找到“最少”的需求量 }

2018-03-23 23:55:40
回复

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会被高亮显示。如果你真的想打“@”这个字符，请用“@@”。