題目描述
設有1g、2g、3g、5g、10g、20g的砝碼各若干枚（其總重 ≤1000），
輸入格式
輸入方式：a1 , a2 ,a3 , a4 , a5 ,a6
（表示1g砝碼有a1 個，2g砝碼有a2 個，…，20g砝碼有a6個）
輸出格式
輸出方式：Total=N
（N表示用這些砝碼能稱出的不同重量的個數，但不包括一個砝碼也不用的情況）
輸入輸出樣例
輸入 #1
1 1 0 0 0 0
輸出 #1
Total=3
解法一：
01揹包思想，總砝碼的範圍是 <=1000, 在這個範圍內，用到了的砝碼組合數標記為1， 未用則為0。這裡可以用三重for迴圈來解決。
第一個for表示砝碼型別數
第二個for表示每種砝碼個數
第三個for為什麼要從1000往前遍歷呢？
在本題中，對於一個成立的重量 w ，一個砝碼的重量 p ，w+p 一定大於 w。 所以這樣就會造成 一個砝碼使用多次的情況 （請認真體會）
解法一程式碼
#include<bits/stdc++.h>
using namespace std;
int x[6] = {1, 2, 3, 5, 10, 20}, a[6], ans;
bool d[1001];
int main() {
for (int i = 0; i < 6; i++)
cin >> a[i];
d[0] = 1;
for (int i = 0; i < 6; i++)
for (int j = 0; j < a[i]; j++)
for (int k = 1000; k >= 0; k--)
if (d[k])
d[k + x[i]] = 1;
for (int i = 1; i <= 1000; i++)
if (d[i])
ans++;
cout << "Total=" << ans;
return 0;
}
解法二
利用bitset，可以快速解決這個問題。
如果不知道bitset的用法可以自己百度哦！
下面這個bitset用法我覺得寫得挺好的
bitset用法
本解核心步驟
意思是將d向左移動我w[i]位，並與之前d取並集
d |= d << x[i]；
d.count()意思是統計d中1的個數
cout << "Total=" << d.count() - 1;
解法二程式碼
#include<bits/stdc++.h>
using namespace std;
int x[6] = {1, 2, 3, 5, 10, 20}, a;
bitset<1001> d;
int main() {
d[0] = 1;
for (int i = 0; i < 6; i++) {
cin >> a;
for (int j = 0; j < a; j++)
d |= d << x[i];
}
cout << "Total=" << d.count() - 1;
return 0;
}