蓝桥杯.砝码称重(01背包)

最近赛训，课程作业，事情一大堆，更新速度有点跟不上了，也是伤脑筋，将就一下吧~

Question:

Solve:

这是一个二次的01背包问题，怎么去想呢？

首先，对于每一个砝码的选择，无非就是三种状态，放在砝码侧，不放该砝码，放在物品侧

假如我只考虑天平的砝码一侧，那这三种状态也就对应的是这个砝码加，不加以及减去该砝码重量

想到这里，基本上就可以理解二次背包了

步骤：

01背包 ： dp[ i ] = 1    (等于1表示重量 i 能称出，等于0表示该重量不能称出)

1.我可以不考虑减去的情况，去把加和不加两种状态做一个dp

2.将上一步整体的dp结果作为一种状态，将减作为另一种状态进行下一次的01背包

3.将两次dp的结果遍历求和，得出所有能称出的重量总数

再稍微解释一下第二步

因为原来的dp结果是加和不加两种状态，那么再次dp所对应的:

某砝码未动  --> 加状态

某砝码原加状态减去 -- >  不加状态

某砝码原不加状态减去 -- > 减去状态

Code:

#include <bits/stdc++.h>
using namespace std;
int w[101], n;
int dp[100010];
int main(void)
{//cincin >>n;for(int i = 1; i <= n; i++) cin >>w[i];memset(dp, 0, sizeof(dp));dp[0] = 1;//第一次01背包(加 | 不加)for(int i = 1; i <= n; i++)for(int j = 100000; j >= w[i]; j--)dp[j] = max(dp[j], dp[j - w[i]]);//二次dp(减状态)for(int i = 1; i <= n; i++)for(int j = 0; j <= 100000 - w[i]; j++)dp[j] = max(dp[j], dp[j + w[i]]);//结果计数long long res = 0;for(int i = 0; i <= 100000; i++)res += dp[i];cout <<res - 1;return 0;
}

最后附上蓝桥杯汇总链接：蓝桥杯C/C++A组省赛历年真题题解 

声明：图片均来源于蓝桥杯官网，以个人刷题整理为目的，如若侵权，请联系删除~