动态规划（5）——01背包问题（NYOJ289苹果）

浏览数：27 / 时间：2015年06月11日

苹果

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

输入

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

输出

对每组测试数据输出一个整数，代表能放入背包的苹果的总价值。

样例输入

样例输出

2
思路：
    就是典型的01背包，用dp[i][j]来代表从第i个苹果到第n个苹果能够装到背包容量为j的最大价值；dp[i][j]=dp[i+1][j]表示，第i个苹果没有装进背包里(第i个苹果的体积比背包的容量大，装不下)；dp[i][j]=max(dp[i+1][j],dp[i+1][j-tiji[i]]+jiazhi[i]);(第i个苹果的体积不大于背包容量，这时就看这个苹果放入背包后的最大价值dp[i+1][j-tiji[i]]+jiazhi[i])和未放入背包时的最大值dp[i+1][j]哪个大就取哪个的值。
AC代码如下：

#include<iostream>
#include<stdio.h>
#include<stdlib.h>
#include<string.h> 
using 
namespace std;
int 
dp[1005][1005];
int 
tiji[1005];
int 
jiazhi[1005];
int 
main()
{
    int 
n,v;
    while(scanf("%d%d",&n,&v))
    {
        if(n==0&&v==0)
            break;
        memset(tiji,0,sizeof(tiji));
        memset(jiazhi,0,sizeof(jiazhi));
        for(int 
i=1;i<=n;i++)
        {
            scanf("%d",&tiji[i]);
            scanf("%d",&jiazhi[i]);        
        }
        memset(dp,0,sizeof(dp));
        int 
jiaoxiao=min(v,tiji[n]-1);
        for(int 
j=0;j<=jiaoxiao;j++)
        {
            dp[n][j]=0;//如果背包容量小于n的体积，那么就只装n苹果而言肯定是装不下。        
        }
        for(int 
j=tiji[n];j<=v;j++)
        {
            dp[n][j]=jiazhi[n];        
        } 
        for(int 
i=n-1;i>1;i--)
        {
             jiaoxiao=min(tiji[i]-1,v);
             for(int 
j=0;j<=jiaoxiao;j++)
             {
                dp[i][j]=dp[i+1][j];//第i个苹果未装入        
             }
             for(int 
j=tiji[i];j<=v;j++)
             {
                 dp[i][j]=max(dp[i+1][j],dp[i+1][j-tiji[i]]+jiazhi[i]);        
             }
        }
        dp[1][v]=dp[2][v];
        if(tiji[1]<=v)
        {
            dp[1][v]=max(dp[2][v],dp[2][v-tiji[1]]+jiazhi[1]);              
        }
        printf("%d\n",dp[1][v]);
    }
    system("pause");
    return 
0;
}