nyist oj 289 苹果 (动态规划——背包问题)

苹果

时间限制:3000 ms  |  内存限制:65535 KB
难度:3
描述

ctest有n个苹果,要将它放入容量为v的背包。给出第i个苹果的大小和价钱,求出能放入背包的苹果的总价钱最大值。


输入
有多组测试数据,每组测试数据第一行为2个正整数,分别代表苹果的个数n和背包的容量v,n、v同时为0时结束测试,此时不输出。接下来的n行,每行2个正整数,用空格隔开,分别代表苹果的大小c和价钱w。所有输入数字的范围大于等于0,小于等于1000。
输出
对每组测试数据输出一个整数,代表能放入背包的苹果的总价值。
样例输入
3 3
1 1
2 1
3 1
0 0
样例输出
2
来源

动态规划经典问题

动态规划中背包的经典问题,以前做过一次了,以前做这种题目的时候,运用的思想是贪心,贪心也可以得到解,但是有时候这个解不是最优的;

运用动态规划思想把这道题在做一次;参考了背包九讲(真的讲的不错,以前有些不懂的地方,现在理解更深了)

这是最基础的背包问题,特点是:每种物品仅有一件,可以选择放或不放。

用子问题定义状态:即f[i][v]表示前i件物品恰放入一个容量为v的背包可以获得的最大价值。则其状态转移方程便是:

f[i][v]=max{f[i-1][v],f[i-1][v-c[i]]+w[i]}

这个方程非常重要,基本上所有跟背包相关的问题的方程都是由它衍生出来的。所以有必要将它详细解释一下:“将前i件物品放入容量为v的背包中”这个子问题,若只考虑第i件物品的策略(放或不放),那么就可以转化为一个只牵扯前i-1件物品的问题。如果不放第i件物品,那么问题就转化为“前i-1件物 品放入容量为v的背包中”,价值为f[i-1][v];如果放第i件物品,那么问题就转化为“前i-1件物品放入剩下的容量为v-c[i]的背包中”,此时能获得的最大价值就是f[i-1][v-c[i]]再加上通过放入第i件物品获得的价值w[i]。

上面的内容引用了背包九讲中的第一讲;这种解法在时间复杂度上是n(nv),比较高效了,但是在空间复杂度上还可以优化;

下面是用最简单的方法写的:空间复杂度还可以优化;动态规划写的程序一般都比较精简,但是就是理解其中的状态表达式;

#include <cstdio>
#include <cstring>
#define max(a,b) a>b?a:b
const int maxn=1001;
int c[maxn],w[maxn],dp[maxn][maxn];
int main()
{
    int n,v,i,j;
    while(scanf("%d%d",&n,&v)&&n&&v)
    {
        memset(dp,0,sizeof(dp));
        for(i=1;i<=n;i++)
            scanf("%d%d",&c[i],&w[i]);
        for(i=1;i<=n;i++)
            for(j=1;j<=v;j++)
        {
            if(j<c[i]) dp[i][j]=dp[i-1][j];//状态表达式
            else
                dp[i][j]=max(dp[i-1][j],dp[i-1][j-c[i]]+w[i]);
        }
        printf("%d\n",dp[n][v]);
    }
}

优化内存的写法,把dp的二维数组换成一维数组,不用数组储存背包的值;用一维数组解背包问题,在后面很多地方也会用到,一定要掌握这种用法;

#include<cstdio>
#include<cstring>
#define max(a,b) a>b?a:b
const int maxn=1001;
int dp[maxn];
int main()
{
    int n,v,i,j,c,w;
    while(scanf("%d%d",&n,&v)&&n&&v)
    {
         memset(dp,0,sizeof(dp));//初始化
         for(i=1;i<=n;i++)
         {
             scanf("%d%d",&c,&w);
             for(j=v;j>=c;j--)
                dp[j]=max(dp[j],dp[j-c]+w);//递推关系
         }
         printf("%d\n",dp[v]);
    }
    return 0;
}




nyist oj 289 苹果 (动态规划——背包问题),布布扣,bubuko.com

nyist oj 289 苹果 (动态规划——背包问题)

上一篇:iOS调试-LLDB


下一篇:android 自动匹配文本 AutoCompleteTextView /MultiAutoCompleteTextView