首页 > 代码库 > 【dp】砝码称重
【dp】砝码称重
砝码称重
来源：NOIP1996（提高组） 第四题
【问题描述】
设有1g、2g、3g、5g、10g、20g的砝码各若干枚（其总重<=1000），用他们能称出的重量的种类数。
【输入文件】
a1 a2 a3 a4 a5 a6
（表示1g砝码有a1个，2g砝码有a2个，…，20g砝码有a6个，中间有空格）。
【输出文件】
Total=N
（N表示用这些砝码能称出的不同重量的个数，但不包括一个砝码也不用的情况）。
【输入样例】
1 1 0 0 0 0
【输出样例】
TOTAL=3
【问题分析】
把问题稍做一个改动，已知a1+a2+a3+a4+a5+a6个砝码的重量w[i], w[i]∈{ 1,2,3,5,10,20} 其中砝码重量可以相等，求用这些砝码可称出的不同重量的个数。
这样一改就是经典的0/1背包问题的简化版了，求解方法完全和上面说的一样，这里就不多说了，只是要注意这个题目不是求最大载重量，是统计所有的可称出的重量的个数。
设dp[1000]数组为标记数组。当dp[i]=0时，表示质量为i的情况，目前没有称出；当dp[i]=1时，表示质量为i的情况已经称出。
本题目中有多个砝码，我们顺序处理每一个砝码。
当处理第j个砝码，质量为wj时，有下列推导公式：
1 #include<iostream> 2 #include<algorithm> 3 #include<string> 4 #include<vector> 5 #include<set> 6 #include<queue> 7 #include<map> 8 #include<stack> 9 #include<iterator>10 #include<cstdio>11 #include<cstring>12 #include<cstdlib>13 #include<cmath>14 using namespace std;15 typedef long long ll;16 typedef unsigned long long ull;17 #define clr(c) memset(c, 0, sizeof(c));18 #define pi acos(-1.0)19 const int INF = 0x3f3f3f3f;20 const int mod = 1e9 + 7;21 const double eps = 1e-8;22 typedef struct point{23 int x, y;24 bool operator < (const point& p) const{25 if (x == p.x) return y < p.y;26 else return x < p.x;27 }28 bool operator >(const point& p) const{29 return p < *this;30 }31 }p;32 int n[10];33 int w[10] = {1, 2, 3, 5, 10, 20};34 int dp[2005];35 int sum, ans;36 37 int main(){38 while(~scanf("%d%d%d%d%d%d", &n[0], &n[1], &n[2], &n[3], &n[4], &n[5])){39 sum = 0;40 for(int i = 0; i < 6; i++) sum += w[i]*n[i];41 memset(dp, 0, sizeof(dp));42 dp[0] = 1;43 for(int i = 0; i < 6; i++){44 for(int j = 0; j < n[i]; j++){45 for(int k = sum; k >= w[i]; k--){46 dp[k] = dp[k-w[i]];47 }48 }49 }50 ans = 0;51 for(int i = 0; i < sum; i++){52 ans += dp[i];53 }54 printf("%d\n", ans);55 }56 57 return 0;58 }
【dp】砝码称重
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。