1 条题解
-
0
#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
- 上传者