设有1g、2g、3g、5g、10g、20g的砝码各若干枚(其总重<=1000),要求:计算用这些砝码能称出的不同重量的个数,但不包括一个砝码也不用的情况。
时间: 2023-04-27 22:01:56 浏览: 115
假设1g、2g、3g、5g、10g、20g的砝码分别有a1、a2、a3、a5、a10、a20枚,且它们的总重不超过100g。
首先,我们可以将所有砝码的重量相加,得到它们的总重量sum。然后,我们可以使用动态规划的思想,定义一个布尔型的二维数组dp,其中dp[i][j]表示使用前i个砝码能否称出重量为j。
初始状态为dp[][]=true,表示不使用任何砝码时可以称出重量为。然后,我们可以使用以下递推式来更新dp数组:
dp[i][j] = dp[i-1][j] || dp[i-1][j-k*wi]
其中,wi表示第i个砝码的重量,k表示第i个砝码使用的枚数,j-k*wi>=且k<=ai。
最后,我们可以遍历dp[6][]数组,统计dp[6][j]=true的个数,即为能够称出的不同重量的个数,但不包括一个砝码也不用的情况。
具体实现可以参考以下代码:
int a[7] = {, a1, a2, a3, a5, a10, a20};
int sum = ;
for (int i = 1; i <= 6; i++) {
sum += i * a[i];
}
bool dp[7][sum+1] = {false};
dp[][] = true;
for (int i = 1; i <= 6; i++) {
for (int j = ; j <= sum; j++) {
for (int k = ; k <= a[i] && k * i <= j; k++) {
dp[i][j] = dp[i][j] || dp[i-1][j-k*i];
}
}
}
int count = ;
for (int j = 1; j <= sum; j++) {
if (dp[6][j]) {
count++;
}
}
return count;