P2347 [NOIP1996 提高组] 砝码称重

题目描述

设有 $1\mathrm{g}$、$2\mathrm{g}$、$3\mathrm{g}$、$5\mathrm{g}$、$10\mathrm{g}$、$20\mathrm{g}$ 的砝码各若干枚（其总重 $ \le 1000$），可以表示成多少种重量？

输入格式

输入方式：$a_1 , a_2 ,a_3 , a_4 , a_5 ,a_6$

（表示 $1\mathrm{g}$ 砝码有 $a_1$ 个，$2\mathrm{g}$ 砝码有 $a_2$ 个，$\dots$，$20\mathrm{g}$ 砝码有 $a_6$ 个）

输出格式

输出方式：Total=N

（$N$ 表示用这些砝码能称出的不同重量的个数，但不包括一个砝码也不用的情况）

样例 #1

样例输入 #1

1 1 0 0 0 0

样例输出 #1

Total=3

题解1：

#include<iostream>
#include<cstring>
#include<cstdio>
#include<cmath>
#include<stdio.h>
#include<vector>//Vector动态容器
#include<algorithm>
#include<stack>//栈
#include<unordered_map>//哈希表
#include<map>
#include<queue>//队列
using namespace std;
int dp[10000001];
int s, n, d;
int w[2000000] = {0,1,2,3,5,10,20};
int val[2000000];
int num[2000000];
int vis[2000000];
int a;
int ans;
int sum = 0;
int main(){
	for (int i = 1; i <= 6; i++){//录入砝码数
		cin >> a;
		sum += a;
		num[i] = a;
	}
	dp[0] = 1;//状态转移的开始 因为不存在一个砝码都不用的情况，所以只能由dp[0]转移
	for (int i = 1; i <= sum; i++) {
		for (int q = 1; q <= num[i]; q++)
			for (int j = 1000; j >= 0; j--){
				if (dp[j] == 1)//如果质量为2成立那么2+2也成立
					dp[j + w[i]] = 1;
			}
	}
	for(int i= 1;i<=1000;i++){
		if (dp[i])
			ans++;
	}
	cout << "Total=" << ans;
}

题解2:

这个题和多重背包如出一辙，但是没有背包问题的“限制”，唯一给的是背包总重不超过1000

那么本蒟蒻就顺手敲了个多重背包的解，但是一开始我也没做出来，我输出的是dp[1000]，过了99%的点。

后来仔细钻研改进，发现了这个题解，

#include<iostream>
#include<cstring>
#include<cstdio>
#include<cmath>
#include<stdio.h>
#include<vector>//Vector动态容器
#include<algorithm>
#include<stack>//栈
#include<unordered_map>//哈希表
#include<map>
#include<queue>//队列
using namespace std;
int dp[10000001];
int s, n, d;
int w[2000000] = {0,1,2,3,5,10,20};
int val[2000000];
int num[2000000];
int vis[2000000];
int a;
int sum = 0;
int ans = 0;
int main(){
	for (int i = 1; i <= 6; i++){//录入砝码数
		cin >> a;
		sum += a;
		num[i] = a;
	}
	for (int i = 1; i <= sum; i++) {
		for (int q = 1; q <= num[i]; q++)
			for (int j = 1000; j >= w[i]; j--){
				dp[j] = max(dp[j], dp[j - w[i]] + w[i]);
			}
	}
	for (int i = 1; i <= 1000; i++)
		if (dp[i] == i)
			ans++;
	cout << "Total=" << ans;
}

原错误题解如下:

#include<iostream>
#include<cstring>
#include<cstdio>
#include<cmath>
#include<stdio.h>
#include<vector>//Vector动态容器
#include<algorithm>
#include<stack>//栈
#include<unordered_map>//哈希表
#include<map>
#include<queue>//队列
using namespace std;
int dp[10000001];
int s, n, d;
int w[2000000] = {0,1,2,3,5,10,20};
int val[2000000];
int num[2000000];
int vis[2000000];
int a;
int sum = 0;
int main(){
	for (int i = 1; i <= 6; i++){//录入砝码数
		cin >> a;
		sum += a;
		num[i] = a;
	}
	for (int i = 1; i <= sum; i++) {
		for (int q = 1; q <= num[i]; q++)
			for (int j = 1000; j >= w[i]; j--){
				dp[j] = max(dp[j], dp[j - w[i]] + w[i]);
			}
	}
	cout << "Total=" << dp[1000];
}

希望有大佬可以给我指点一二，为什么原题解不对