砝碼稱重
問題描述
你有一架天平和 N 個砝碼，這 N 個砝碼重量依次是 W1,W2,???,WN。
請你計(jì)算一共可以稱出多少種不同的正整數(shù)重量？
注意砝碼可以放在天平兩邊。
輸入格式
輸入的第一行包含一個整數(shù) N。
第二行包含 N 個整數(shù)：W1,W2,W3,???,WN。
輸出格式
輸出一個整數(shù)代表答案。
數(shù)據(jù)范圍
對于 50% 的評測用例，1≤N≤15。
對于所有評測用例，1≤N≤100，N 個砝碼總重不超過 100000。
輸入樣例：
3
1 4 6
輸出樣例：
10
樣例解釋
能稱出的 10 種重量是：1、2、3、4、5、6、7、9、10、11。
1 = 1；
2 = 6 ? 4 (天平一邊放 6，另一邊放 4)；
3 = 4 ? 1；
4 = 4；
5 = 6 ? 1；
6 = 6；
7 = 1 + 6；
9 = 4 + 6 ? 1；
10 = 4 + 6；
11 = 1 + 4 + 6。
?
題解：
????????首先，我們知道一個常理（常理：左面放物品，右面放砝碼），然后再去分析問題。
????????本題解法是動態(tài)規(guī)劃。動態(tài)規(guī)劃的根本是找到狀態(tài)轉(zhuǎn)移方程。
????????狀態(tài)轉(zhuǎn)移方程，顯然包括兩個方面，“狀態(tài)”，“轉(zhuǎn)移”。那么我們先找到狀態(tài)。
狀態(tài)：
? ? ? ? 根據(jù)日常稱物品時候的經(jīng)驗(yàn)，不同的重量的物品所需要的砝碼的數(shù)量是不同的，我們就可以考慮這個砝碼用不用作為判斷的狀態(tài)。
轉(zhuǎn)移：
? ? ? ? 假如現(xiàn)在拿的是第i個砝碼，那么這個砝碼的命運(yùn)有三種：（天平有兩個盤子）
? ? ? ? ? ? ? ? 不放、放左邊、和放右邊
? ? ? ? 我們規(guī)定dp[i][j]表示只用前i個砝碼所能稱重量為j 的可行性（true、folse）
那么可以得到：
????????不放：f[i-1][j]
? ? ? ? 放左邊：f[i-1][abs(j-w[i])]
? ? ? ? 放右邊：f[i-1][j+w[i]]
所以狀態(tài)轉(zhuǎn)移方程為
? ? ? ? f[i][j]=f[i-1][j]||f[i-1][abs(j-w[i])]||f[i-1][j+w[i]]
代碼如下：
#include<iostream>
#include<math.h>
using namespace std;
const int N=110,M=2e5+10;
int n,sum,w[N];
int f[N][M];
int main()
{
cin>>n;
for(int i=1;i<=n;i++)
{
cin>>w[i];
sum+=w[i];
}
f[0][0]=true;
for(int i=1;i<=n;i++)
{
for(int j=0;j<=sum;j++)
{
f[i][j]=f[i-1][j]||f[i-1][j+w[i]]||f[i-1][abs(j-w[i])];
}
}
int ans=0;
for(int j=1;j<=sum;j++)
{
if(f[n][j])ans++;
}
cout<<ans;
return 0;
} ????????文章來源：http://www.zghlxwxcb.cn/news/detail-403825.html
?文章來源地址http://www.zghlxwxcb.cn/news/detail-403825.html
到了這里，關(guān)于試題 歷屆真題 砝碼稱重【第十二屆】【省賽】【B組】的文章就介紹完了。如果您還想了解更多內(nèi)容，請?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
![[藍(lán)橋杯嵌入式]STM32G431——第十二屆第一場省賽停車計(jì)費(fèi)系統(tǒng)真題及程序設(shè)計(jì)代碼詳解](https://imgs.yssmx.com/Uploads/2024/01/799528-1.jpeg)
