【题目描述】
设有 1g 、 2g 、 3g 、 5g 、 10g 、 20g 的砝码各若干枚（其总重 <= 1000 ）
【输入】
输入方式：\(a_1,a_2,a_3,a_4,a_5,a_6\)
表示 1g 砝码有 \(a_1\) 个， 2g 砝码有 \(a_2\) 个， ··· ， 20g 砝码有 \(a_6\) 个
【输出】
输出一个正整数 \(N\), 表示用这些砝码能称出的不同重量的个数，但不包括一个砝码也不用的情况
【输入样例】
1 1 0 0 0 0
【输出样例】
3
【代码详解】
#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;int cur, a[1005], cnt; // cur: 砝码总个数，a: 存储所有砝码重量，cnt: 可称出的不同重量数
bool dp[1005][1005]; // dp[i][j]: 用前i个砝码能否称出重量j
int b[7] = {0, 1, 2, 3, 5, 10, 20}; // 不同种类砝码的重量int main()
{// 读入6种砝码的数量，并展开为单个砝码数组for (int i = 1; i <= 6; i++){int x; // 第i种砝码的数量cin >> x;for (int j = 1; j <= x; j++){a[++cur] = b[i]; // 将每个砝码按重量放入数组}}// 调试输出// for (int i=1;i<=cur;i++)// cout<<a[i]<<' ';dp[0][0] = 1; // 不使用任何砝码可以称出重量0// 动态规划：01背包问题for (int i = 1; i <= cur; i++) // 遍历每个砝码{for (int j = 0; j <= 1000; j++) // 遍历所有可能的重量{dp[i][j] = dp[i - 1][j]; // 不使用第i个砝码if (j >= a[i]) // 如果当前重量j大于等于第i个砝码的重量{dp[i][j] |= dp[i - 1][j - a[i]]; // 使用第i个砝码}}}// 统计能称出的不同正重量数for (int j = 1; j <= 1000; j++){cnt += dp[cur][j]; // 如果能称出重量j，计数器加1}cout << cnt; // 输出可称出的不同重量数return 0;
}
【运行结果】
1 1 0 0 0 0
3