1 条题解

  • 1
    @ 2024-09-29 16:07:14

    普通背包: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;
    }
    
  • 1

信息

ID
1070
难度
9
分类
(无)
标签
(无)
递交数
1
已通过
1
通过率
100%
上传者