POJ 1742 Coins 多重背包(二進制優化/可行性分析)

優化：

當v[i] * num[i] >= weight時，該物品即可做完全背包處理

其他情況用二進制優化做01背包處理 

#include <cstdio>
#include <algorithm>
#include <iostream>
#include <string>
#include <cstring>
#include <vector>
#include <map>
#include <queue>
#define INF 0x3f3f3f3f
using namespace std;
typedef long long ll;
static const ll Mod = 1e9 + 7;
static const int MAX_N = 1e5 + 5;
bool dp[MAX_N];
int v[105], num[105];
void comple_pack(int x, int weight) {
	for (int j = x; j <= weight; ++j) {
		if (dp[j - x]) dp[j] = true;
	}
}
void zero_one_pack(int x, int weight) {
	for (int j = weight; j >= x; --j) {
		if (dp[j - x]) dp[j] = true;
	}
}
int main() {
	/*freopen("input.txt", "r", stdin);
	freopen("output.txt", "w", stdout);*/
	int n, weight;
	while (scanf("%d%d", &n, &weight) != EOF) {
		if (n == 0 && weight == 0) break;
		for (int i = 0; i < n; ++i) scanf("%d", &v[i]);
		for (int i = 0; i < n; ++i) scanf("%d", &num[i]);
		for (int i = 1; i <= weight; ++i) dp[i] = false;
		dp[0] = true;
		for (int i = 0; i < n; ++i) {
			if (v[i] * num[i] >= weight) comple_pack(v[i], weight);
			else {
				for (int j = 1; j <= num[i]; j <<= 1) {
					if (v[i] * j <= weight) zero_one_pack(v[i] * j, weight);
					num[i] -= j;
				}
				if (num[i] > 0 && v[i] * num[i] <= weight) zero_one_pack(v[i] * num[i], weight);
			}
		}
		int res = 0;
		for (int i = 1; i <= weight; ++i) if (dp[i]) ++res;
		printf("%d\n", res);
	}
	return 0;
}
           

多重背包的可行性分析

#include <cstdio>
#include <algorithm>
#include <iostream>
#include <string>
#include <cstring>
#include <vector>
#include <map>
#include <queue>
#define INF 0x3f3f3f3f
using namespace std;
typedef long long ll;
static const ll Mod = 1e9 + 7;
static const int MAX_N = 1e5 + 5;
bool dp[MAX_N];
int use[MAX_N];
int v[105], num[105];
int main() {
	/*freopen("input.txt", "r", stdin);
	freopen("output.txt", "w", stdout);*/
	int n, weight;
	while (scanf("%d%d", &n, &weight) != EOF) {
		if (n == 0 && weight == 0) break;
		for (int i = 0; i < n; ++i) scanf("%d", &v[i]);
		for (int i = 0; i < n; ++i) scanf("%d", &num[i]);
		for (int i = 1; i <= weight; ++i) dp[i] = false;
		dp[0] = true;
		for (int i = 0; i < n; ++i) {
			for (int j = 1; j <= weight; ++j) use[j] = 0;
			for (int j = v[i]; j <= weight; ++j) {
				if (dp[j - v[i]] && !dp[j] && use[j - v[i]] < num[i]) {
					use[j] = use[j - v[i]] + 1;
					dp[j] = true;
				}
			}
		}
		int res = 0;
		for (int i = 1; i <= weight; ++i) if (dp[i]) ++res;
		printf("%d\n", res);
		
	}
	return 0;
}