题解 | #点菜问题#

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));
    }
}