小 $C$ 到商店购物，她只带了 $SW$ 元钱。有 $n$ 件商品，第 $i$ 件商品的价格为 $w_i$ 元，小 $C$ 对它的满意度为 $v_i$ 。小 $C$ 想要知道，用自己仅有的 $SW$ 元钱，能买到的所有商品的满意度之和最大是多少。
数据保证 $1 \leq n,w_i,v_i \leq 100, 1 \leq SW \leq 10000$
#include <iostream>
using namespace std;
const int INF = 0x3f3f3f3f;
int n, SW, W[105], V[105], Dp[___(1)___];
int main(){
cin >> n >> SW;
for (int i = 1; i <= n; i++)
cin >> W[i] >> V[i];
for (int i = 1; i <= SW; i++)
Dp[i] = ___(2)___;
for (int i = 1; i <= n; i++)
for (___(3)___)
Dp[j] = max(Dp[j], ___(4)___);
int ans = 0;
for (int i = 1; i <= SW; i++)
___(5)___;
cout << ans << "\n";
return 0;
}
1. D。 $1 \leq SW \leq 10000$，故要选择 $> 10000$ 的数
2. B。 初始化为 $0$。
3. A。 从大到小枚举背包大小。
4. C。 维护当前背包大小为 $j$，要购买第 $i$ 件物品的最大满意度
5. A。 找最大值