题解
【基础】砝码称重
1 条题解
-
0
#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