poj 1384 完全背包

￡神魔★判官ぃ 2021-12-17 02:57 211阅读 0赞

记住这个公式就OK了。for i=1..N for v=w\[i\]..V f\[v\]=max\{f\[v\],f\[v-w\[i\]\]+v\[i\]\}.这样就转换成为了0/1背包问题是一样的，只不过第二个循环的顺序不一样而已。

![2012051921435185.png][]

#include<iostream>
    #include <fstream>
    
    #define  MIN(a,b) (a<b?a:b)
    #define INF 9999999
    #define MAXN 505
    #define MAX 10001
    using namespace std;
    int t,n,d,e,g;
    int v[MAXN],w[MAX],f[MAX];
    
    int main()
    {
        int i,j;
        freopen("in.txt","r",stdin);
        scanf("%d",&t);
        while(t--)
        {
            scanf("%d%d",&e,&g);
            d=g-e;
            for(i=1; i<=d; i++)  //因为是求最小的，所以这里要设成最大
            {
                f[i]=INF;
            }
            scanf("%d",&n);
            for(i=1; i<=n; i++)
            {
                scanf("%d%d",&v[i],&w[i]);
            }
            for(i=1; i<=n; i++)
            {
                for(j=w[i]; j<=d; j++)  //注意这里 从w[i]开始。前面的是没必要的
                {
                    f[j]=MIN(f[j],f[j-w[i]]+v[i]);
                }
            }
            if(f[d]==INF)
            {
                printf("This is impossible.\n");
            }
            else
            {
                printf("The minimum amount of money in the piggy-bank is %d.\n",f[d]);
            }
        }
        return 0;
    }

转载于:https://www.cnblogs.com/Jason-Damon/archive/2012/05/19/2507135.html

[2012051921435185.png]: /images/20211214/3b973b807e434f33a725ee4737ebf34e.png

发表评论取消回复

表情：

评论列表（有 0 条评论，211人围观）

还没有评论，来说两句吧...

相关阅读

相关 nyoj 311 完全背包（dp--完全背包）

完全背包时间限制： 3000 ms | 内存限制： 65535 KB 难度： 4 描述直接说题意，完全背包定义有N种物品和一个容量为V的背包，每种物品都有无限件

系统管理员/ 2024年02月17日 20:51/ 0 赞/ 14 阅读

相关完全背包

完全背包在背包九讲中有很详细的讲解，但是今天碰到题尝试了一下他给的算法，发现并不快，看了一下其他的代码，速度很快！题目链接http://hihocoder.com/prob

拼搏现实的明天。/ 2022年08月21日 02:16/ 0 赞/ 206 阅读

相关 Dollar Dayz POJ - 3181 动态规划完全背包

Farmer John goes to Dollar Days at The Cow Store and discovers an unlimited number of

向右看齐/ 2022年06月17日 11:41/ 0 赞/ 146 阅读

相关完全背包 POJ - 2063 

John never knew he had a grand-uncle, until he received the notary's letter. He learn

淩亂°似流年/ 2022年06月17日 09:40/ 0 赞/ 167 阅读

相关 01背包,完全背包

01背包问题：一个背包总容量为V，现在有N个物品，第i个物品体积为weight\[i\]，价值为value\[i\]，现在往背包里面装东西，怎么装能使背包的内物品价值最大？

男娘i/ 2022年06月09日 04:16/ 0 赞/ 268 阅读

相关完全背包

完全背包和01背包的区别 > 01背包：有n个物品，每种物品只能被使用一次 > > 完全背包：有n个物品，每个物品可以被多次使用完全背包的递推公式可以由01背包的递推公

ゞ浴缸里的玫瑰/ 2022年06月08日 09:43/ 0 赞/ 207 阅读

相关完全背包

问题：有N种物品和一个容量为V的背包，每种物品都有无限件可用。第i种物品的费用是c\[i\]，价值是w\[i\]。求解将哪些物品装入背包可使这些物品的费用总和不超过背包容量

今天药忘吃喽~/ 2022年05月31日 01:05/ 0 赞/ 215 阅读

相关背包问题—01背包、完全背包

01背包问题题目有m件物品和一个容量为V 的背包。放入第i 件物品占用的体积是Vi，得到的价值是Wi。求解将哪些物品装入背包可使价值总和最大。思路这

末蓝、/ 2022年05月30日 10:10/ 0 赞/ 386 阅读

相关 POJ 2229 Sumsets————（完全背包 or 规律）

Sumsets Time Limit: 2000MS Memory Limit: 200000K Total Submissions: 23184 Accepted:

男娘i/ 2022年05月18日 04:36/ 0 赞/ 163 阅读

相关 poj 1384 完全背包

记住这个公式就OK了。for i=1..N for v=w\[i\]..V f\[v\]=max\{f\[v\],f\[v-w\[i\]\]+v\[i\]\}.这样就转换成为了

￡神魔★判官ぃ/ 2021年12月17日 02:57/ 0 赞/ 212 阅读