top1编程
← 返回题目
题解

【基础】砝码称重

1 条题解

  • 0
    @ 2026-7-29 0:18:09
    #include<bits/stdc++.h>
    using namespace std;
    //砝码称重(多重背包)
    int dp[1010],w1[7]={0,1,2,3,5,10,20},w[1000],p;
    int main(){
    	for(int i=1;i<=6;i++){
    		int s;
    		cin>>s;//输入该重量下的砝码数量
    		int t=1;//权值
    		while(1){
    			if(s>t){
    				w[++p]=w1[i]*t;//将对应的组成新重量放到w数组中
    				s-=t;//减少数量
    				t*=2;//权值更新
    			}else{
    				w[++p]=w1[i]*s;//将剩余的砝码组成一个新的放到w数组中
    				break;
    			}
    		}
    	}
    	dp[0]=1;//什么都没有情况有1中
    	for(int i=1;i<=p;i++){
    		for(int j=1000;j>=w[i];j--){
    			//现在j=10的情况 那现在有一大小为5的砝码
    			//判断这个砝码与其他之前砝码能不能组成10
    			//要组成10 现在要把5塞进去 说明在此之前dp[5]必须不等于0
    			if(dp[j-w[i]]) dp[j]=1;//标记当前这一个重量
    		}
    	}
    	int cnt=0;
    	for(int i=1;i<=1000;i++){//在1~1000的范围内去判断那些被标记
    		if(dp[i]) cnt++;
    	}
    	cout<<cnt;
    	return 0;
    }
    
    • 1