题解 | #最小邮票数#

#include <cstdio>
#include <iostream>
#include <cstring>
#include <climits>

using namespace std;

//这题如何类比0-1背包？
//个人思路：“价值最大”在这题转化为“邮票张数最小” 可以这样转化：每张邮票价值为-1 完美
//0-1背包中，是可以不塞满的，这题必须塞满，这个怎么办？这是真正的难点。

const int MAXM = 100 + 10;
const int MAXN = 20 + 2;
const int INF = INT_MAX;

int dp[MAXM];
int w[MAXN];//存“分数” 
int v[MAXN];//存“-1”

int main(){
	memset(v, -1, sizeof(v));
	int m, n;
	while(scanf("%d%d", &m, &n) != EOF){
		memset(dp, 0, sizeof(dp));
		for(int i=1; i<=n; i++){
			scanf("%d", &w[i]);
		}
		for(int i=1; i<=n; i++){
			for(int j=m; j>=w[i]; j--){
				int a = dp[j];
				int b = dp[j-w[i]] + v[i];//注意一个逻辑。dp[j-w[i]]是凑成了j-w[i]分，而v[i]对应w[i]分，加起来刚好是j 
				//所以单论这里是不用去做总和检验的。
				//那总和是怎么保证的呢？ 个人思路：检测“初始状态”
				if(a == 0){//在遇到第i个元素前，都没有可行的放法 那一旦b可行，a就应该让步 
					a = -INF;
				}
				if(dp[j-w[i]] == 0){//说明对应容量j-w[i]，用前i-1个元素没有放法，只能期待w[i]本身就等于j 
					if(w[i] == j){
						;//b就可以维持原样 
					}else{
						b = -INF;//不可行 
					}
				} 
				dp[j] = max(a, b);
				if(dp[j] == -INF){//意味着“不可行” 
					dp[j] = 0;
				}//所以最终其实用不到vector
			}
		}
		printf("%d\n", -dp[m]);
	}
	return 0;
}