1 条题解

  • 0
    @ 2026-1-27 21:26:17
    #include<bits/stdc++.h>
    using namespace std;
    
    // [1] dp数组-标记重量k是否能被称出(1=可以,0=不行),数组大小10010是因为题目规定总重量≤1000
    int dp[10010]={};
    struct stu{
        // [2] weight-砝码的单个重量;num-该种砝码的数量
        int weight,num;
    }arr[10];  // [3] arr数组-存储6种砝码(1g~20g)的重量和数量,下标1-6对应1g到20g
    
    int main(){
        // 问题分析:多重背包变种问题,给定6种砝码的数量,计算能称出的不同重量个数(不含0重量)
        // 解题步骤:1.初始化6种砝码的重量;2.读入每种砝码的数量并计算总重量;3.用dp数组标记重量是否可达;
        //          4.将每种砝码拆成单个物品做01背包(三重循环);5.统计可达重量的数量(不含0)
        
        // 初始化6种砝码的重量(1g、2g、3g、5g、10g、20g)
        arr[1].weight=1,arr[2].weight=2,arr[3].weight=3,arr[4].weight=5,arr[5].weight=10,arr[6].weight=20;
        int sum=0;  // [4] sum-所有砝码的总重量,用于限制dp数组的遍历范围
        
        // 读入每种砝码的数量,并计算总重量
        for(int i=1;i<=6;i++){
            cin>>arr[i].num;  // [5] 读入第i种砝码的数量
            sum+=arr[i].weight*arr[i].num;  // [6] 累加计算所有砝码的总重量
        }
        
        dp[0]=1;  // [7] 初始化:0重量(不用任何砝码)是可以称出的
        
        // 处理每种砝码,拆成单个物品做01背包(三重循环)
        for(int i=1;i<=6;i++){  // [8] 外层循环:遍历6种砝码
            for(int j=1;j<=arr[i].num;j++){  // [9] 中间循环:遍历当前砝码的数量(拆成单个物品)
                // 内层循环:逆序遍历重量(01背包核心,避免重复选取同一砝码)
                for(int k=sum;k>=arr[i].weight;k--){
                    // [10] 状态转移:如果k-当前砝码重量可达,那么k重量也可达
                    if(dp[k-arr[i].weight]) dp[k]=1;
                }
            }
        }
        
        // 统计能称出的不同重量个数(不含0重量)
        int num_sum=0;  // [11] num_sum-存储能称出的不同重量个数
        for(int i=1;i<=sum;i++){
            if(dp[i]) num_sum++;  // [12] 遍历1~sum,统计可达重量的数量
        } 
        
        cout<<num_sum;  // [13] 输出结果:能称出的不同重量个数
        return 0;
    }
    
    • 1

    信息

    ID
    1340
    时间
    1000ms
    内存
    256MiB
    难度
    10
    标签
    递交数
    1
    已通过
    1
    上传者