普通背包：P1002 灰灰的婚姻

当\(w\)权值过大导致无法开对应大小的数组时，如果\(v\)范围较小，可以考虑用\(v\)价值来开数组。

设\(dp[i][j]\)表示 “只考虑前\(i\)个物品的 情况下，总价值是\(j\)所需的最小容量”。那么在计算\(dp[i][j]\)的时候，所有情况 依然可以分成两类考虑：

• 拿第\(i\)件物品，那么别的物品的总价值需要凑出\(j−v_i\)，而由于每样物品只能拿一件，所以我们只需要考虑前\(i−1\)件物品的最优选取方式，即最终重量为\(dp[i−1][j−v_i]+wi\)。

• 不拿第\(i\)件物品，那么别的物品需要凑出\(j\)的价值。由于我们选择不拿第\(i\)件物品，现在只需要考虑前\(i−1\)件物品的最优选取方式，即最小重量为\(dp[i−1][j]\)。

计算完所有状态的值后，只需要选取满足重量上限的最大价值即可。

然后呢，我们还可以参照01背包的方法，将状态转移方程压成1维。

故，我们可得本题的状态转移方程为：\(dp[j]=min(dp[j],dp[j−v[i]]+w[i])\)

代码如下

#include <bits/stdc++.h>
#define MAXN 100005
#define INF 1e9
#define FILE_IO false
#define DISCONNECT_WITH_STDIO true
using namespace std;

int f[100005], w[101], v[101], N, W, maxValue;

int main() {
    cin>>N>>W;
    for(int i=1; i<=N; i++){
        cin>>w[i]>>v[i];
    }
    memset(f, 0x3f, sizeof f);
    f[0] = 0;
    maxValue = N*1000;
    
    for(int i=1; i<=N; i++){
        for(int j=maxValue; j>=v[i]; j--){
            f[j] = min(f[j], f[j-v[i]]+w[i]);
        }
    }
    
    for(int i=maxValue; i; i--){
        if (f[i] <= W){
            cout<<i;
            return 0;
        }
    }
    
    return 0;
}