题解

思路

这道题特殊的一点是需要解决的问题是求最小值，这就需要初始化dp数组元素为一个极大值。

还有一点就是题目细节：这道题要求的是最终物品重量“不小于”L，导致了这道题循环背包容量的时候需要循环到1。（本蒟蒻在这里吃尽苦头）

状态定义：dp[j] = 容量不小于 j 的最小花费

状态转移方程：

1. 当 j > r[i] ：代表当前枚举的背包容量可以装下该物品。方程：dp[j] = min(dp[j], dp[j - r[i] + c[i])；
2. 当 j <= r[i] ：代表当前枚举的背包容量不足与装下当前物品。方程： dp[j] = min(dp[j], 0 + c[i]；（其中 0 代表不选其他任何物品，只装当前大于背包容量的这个物品，因为如果当前物品不大于当前背包容量，除了放下当前物品还可以获得价值 dp[j - r[i]] ，而如果选择了当前这个大于背包容量的物品就没有可以额外获得的价值了，所以 + 0）

总的来看，状态转移方程为 dp[j] = min(dp[j], dp[max(j - r[i], 0] + c[i].（通过 dp[0] = 0 间接得到 0 ）

代码

#include<bits/stdc++.h>
using namespace std;

const int INT=1e8; //极大值，既方便后续取最小值，又方便这道题 ”no solution" 的情况
int n,l,c[510],r[510],dp[510]; //c为物品价值，r为物品重量

int main(){
	cin>>n>>l;
	for(int i=1;i<=n;i++) cin>>c[i]>>r[i];
	
	for(int i=1;i<=l;i++) dp[i]=INT; //初始化为极大值

    dp[0]=0; //极为重要，因为后续当 j < a[i] 时需要 dp[0] 为 0 的值
	for(int i=1;i<=n;i++){
		for(int j=l;j>=1;j--){ //满足题意极为重要的一点：j >= 1可以枚举到不小于 L 的情况
			dp[j]=min(dp[j],dp[max(j-r[i],0)]+c[i]);
		}
	}
	
	if(dp[l]==INT) cout<<"no solution";
	else cout<<dp[l];
	
	return 0;
}

题外话

提交完后突然有一个“空间掌控者”直接贴脸，也是戴上了awa

自己做的题不能得到这些徽章吗，不知道什么时候才能获得“时间掌控者”qwq