跳至正文

tyvj 1005 采药

  • OI路程

  01背包的例子,不过第一次写的时候不小心把01背包写成了无限背包,代码如下:

#include <stdio.h>
#define max(a, b) ((a)>(b)?(a):(b))
int f[1001];

int main(void)
{
        int i, j;
        int t, m;
        int a, b;
        scanf("%d%d", &t, &m);
        for(i = 0; i < m; i++){
                scanf("%d%d", &a, &b);
                /
                Mistack 1:
                  把01背包写成了无限背包 
                
/
/              for(j = a; j <= t; j++){
                        f[j] = max(f[j], f[j – a] + b);
                }
/
                for(j = t; j >= a; j–){
                        f[j] = max(f[j], f[j – a] + b);
                }
        }
        printf("%d\n", f[t]);
        return 0;
}

发表评论

您的电子邮箱地址不会被公开。