题解：B3873 [GESP202309 六级] 小杨买饮料

前言

一道~~非常简单的~~ 01 背包变形。

简述

小杨来到一家商店买饮料，商店有

N

种饮料，编号

0

到

N-1

。第

i

种饮料的价格是

c_i

元，容量是

l_i

毫升。小杨的要求是：

每种饮料最多买 $1$ 瓶。
购买的饮料总容量至少为 $L$ 毫升。
在满足前两个条件的情况下花费最少。

如果无法满足条件，输出 no solution。

本题思路

本题是一个相对简单的背包，目标是选择若干种不同的饮料，使得它总容量至少为

L

毫升，并且总花费最小。

由于每种饮料只有选或不选两种情况，可以用 01背包求解。

首先，定义

dp _ {i,j}

表示从前

i

种饮料中选择，使得总容量至少为

j

毫升时的最小花费。

初始化时，要使 dp[0][0]=0（什么也不选也是

1

种方案），

dp

数组其余设为无穷大（因为要找最小值）。

接下来，遍历每种饮料，并考虑选或不选它：

1.不选第

i

种饮料：dp[i][j] = dp[i-1][j]，直接从之前的状态继承。

2.选第

i

种饮料：

如果该饮料的容量

l[i]

已经满足

j

，则只需要花费

c[i]

元。否则，还需要从前

i-1

种饮料中补充

j-l[i]

的容量，即 dp[i][j]=dp[i-1][j-l[i]]+c[i]。

当然，为了避免

j-l[i]

为负数，我们取 prev=max(0,j-l[i])，确保剩余需求不会小于

0

。

最终，

dp[N][L]

就是答案：如果它仍然是无穷大，说明无法满足需求，输出 no solution；否则，输出

dp[N][L]

。

代码

CPP

#include<bits/stdc++.h>
using namespace std;
int N,L,c[505],l[505],dp[505][2005]//前 i 种饮料中选，使得总容量至少为 j 毫升时的最小花费。
int main(){
	cin>>N>>L;
	for(int i=1;i<=N;i++){
		cin>>c[i]>>l[i];
	}
	memset(dp,0x3f,sizeof(dp));
	dp[0][0]=0;//什么也不选也是 1 种方案。 
	for(int i=1;i<=N;i++){
		for(int j=0;j<=L;j++){
			//不选。 
			 dp[i][j]=dp[i-1][j];
            //选第 i 种饮料。
            int prev=max(0,j-l[i]);//目标不是恰好装满，而是至少达到 L 容量。
            if(dp[i-1][prev]+c[i]<dp[i][j]){
                dp[i][j]=dp[i-1][prev]+c[i];
            }
		} 
	}
	if(dp[N][L]!=0x3f3f3f3f){//被更新。 
		cout<<dp[N][L];
	}else{
		cout<<"no solution";//未被更新。
	}
	return 0;
}

题解：B3873 [GESP202309 六级] 小杨买饮料

文章操作

前言

简述

本题思路

代码

相关推荐

评论

题解：B3873 [GESP202309 六级] 小杨买饮料