题解 | #点菜问题#

点菜问题

http://www.nowcoder.com/questionTerminal/b44f5be34a9143aa84c478d79401e22a

0-1背包

每种物品只有一个,物品i的体积:w[i]、价值:v[i]

dp[i][j]:前i个物品装进容量为j的背包所获得的最大价值

  • ① 不放第i个物品 dp[i][j]=dp[i-1][j]
  • ② 放入第i个物品 dp[i][j]=dp[i-1][j-w[i]]+v[i]
#include<iostream>
using namespace std;
const int maxn=1001;
int w[maxn];
int v[maxn];
int dp[maxn][maxn];

int best(int sum,int n){
    for(int i=0;i<=n;i++){//初始化
        dp[i][0]=0;
    }
    for(int i=0;i<=sum;i++){
        dp[0][i]=0;
    }
    
    for(int i=1;i<=n;i++){
        for(int j=1;j<=sum;j++){
            if(w[i]>j)dp[i][j]=dp[i-1][j];
            else dp[i][j]=max(dp[i-1][j],dp[i-1][j-w[i]]+v[i]);
        }
    }
    return dp[n][sum];
}


int main(){
    int sum,n;
    while(scanf("%d%d",&sum,&n)!=EOF){
        for(int i=1;i<=n;i++)scanf("%d%d",&w[i],&v[i]);//注意从1开始放,0留作边界
        printf("%d\n",best(sum,n));
    }
}

优化:压缩空间

  • dp[i][j]每行只取决于上一行前面部分的值
  • 故从后往前更新
#include<iostream>
using namespace std;
const int maxn=1001;
int w[maxn];
int v[maxn];
int dp[maxn];//只保存一行状态(容量:0~sum)

int best(int sum,int n){
    
    for(int i=0;i<=sum;i++){//初始化
        dp[i]=0;
    }
    
    for(int i=1;i<=n;i++){
        for(int j=sum;j>=w[i];j--){//从后往前更新
             dp[j]=max(dp[j],dp[j-w[i]]+v[i]);
        }
    }
    return dp[sum];
}


int main(){
    int sum,n;
    while(scanf("%d%d",&sum,&n)!=EOF){
        for(int i=1;i<=n;i++)scanf("%d%d",&w[i],&v[i]);//注意从1开始放,0留作边界
        printf("%d\n",best(sum,n));
    }
}
全部评论

相关推荐

点赞 评论 收藏
转发
点赞 收藏 评论
分享
牛客网
牛客企业服务