Stamps and Envelope Size UVA

完全背包问题

附一篇完全背包问题很好的讲解blogs./Kalix/p/7622102.html

01背包也值得一看blogs./Kalix/p/7617856.html

代码也好理解

#include<iostream>
#include<cmath>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<iomanip>
#include<assert.h>
#include<vector>
#include<list>
#include<map>
#include<set>
#include<sstream>
#include<stack>
#include<queue>
#include<string>
#include<bitset>
#include<algorithm>
#pragma warning(disable:4996)
#define me(s)  memset(s,0,sizeof(s))
#define _for(i,a,b) for(int i=(a);i<(b);++i)
#define _rep(i,a,b) for(int i=(a);i<=(b);++i)
#define FOR(i,n) for(int i=(n);i>=0;i--)
using namespace std;
typedef pair <int, int> pii;
typedef long long ll;
typedef unsigned long long llu;
const int inf = 0x3f3f3f3f;
const int dr[] = { 0, -1, 0, 1, -1, -1, 1, 1 };
const int dc[] = { -1, 0, 1, 0, -1, 1, -1, 1 };
const int MOD = 1e9 + 7;
const double pi = acos(-1.0);
const double eps = 1e-15;
const int maxn = 25;
int s, n, m;
int a[maxn];
int dp[1005];
int ans[maxn];
int main()
{while (cin >> s && s){int best = 0, Max =  inf, num = inf;cin >> n;for (int i = 0; i < n; i++){cin >> a[0];for (int j = 1; j <= a[0]; j++)cin >> a[j];memset(dp, 100, sizeof(dp));dp[0] = 0;int now = 0;for (int j = 1; j <= s * a[a[0]] + 1; j++){for (int k = 1; k <= a[0] && j >= a[k]; k++)dp[j] = min(dp[j], dp[j - a[k]] + 1);if (dp[j]>s){now = j - 1;break;}}if (now > best)   {best = now; num = a[0];Max = a[a[0]];memcpy(ans, a, sizeof(a));}else if (now == best)   {if (a[0] < num)   {num = a[0];Max = a[a[0]];memcpy(ans, a, sizeof(a));}else if (a[a[0]] < Max)  {Max = a[a[0]];memcpy(ans, a, sizeof(a));}}}printf("max coverage =%4d :", best);for (int i = 1; i <= num; i++)printf("%3d", ans[i]);puts("");}
}