題意：給出幾種面值的錢幣和對應的個數，看能否湊出1-m中的各個面值。
分析：顯然，多重背包問題。要求全部裝滿。而且對1-m遍歷並計數，毫無壓力~
上代碼：
[cpp] #include <iostream>
using namespace std;
int MIN_INT = (~(unsigned(-1)>>1));
int F[100001];
int A[101];
int C[101];
int max(int a, int b)
{
return a>b?a:b;
}
void ZeroOnePack(int cost, int weight, int V)
{
for (int v=V; v>=cost; --v)
F[v] = max(F[v], F[v-cost]+weight);
}
void CompletePack(int cost, int weight, int V)
{
for (int v=cost; v<=V; ++v)
F[v] = max(F[v], F[v-cost]+weight);
}
void MultiPack(int cost, int weight, int V, int amount)
{
if (cost*amount>=V) {
CompletePack(cost, weight, V);
return;
}
int k = 1;
while (k<amount) {
ZeroOnePack(cost*k, weight*k, V);
amount -= k;
k *= 2;
}
ZeroOnePack(cost*amount, weight*amount, V);
}
int main(int argc, char **argv)
{
int n, m, count;
while ((cin>>n>>m) && (m+n)) {
for (int i=1; i<=n; ++i)
cin>>A[i];
for (int i=1; i<=n; ++i)
cin>>C[i];
count = 0;
for (int V=1; V<=m; ++V) {
F[0] = 0;
for (int i=1; i<=m; ++i)
F[i] = MIN_INT;
for (int i=1; i<=n; ++i)
MultiPack(A[i], A[i], V, C[i]);
if (F[V]==V)
++count;
}
cout<<count<<endl;
}
system("pause");
return 0;
}
#include <iostream>
using namespace std;
int MIN_INT = (~(unsigned(-1)>>1));
int F[100001];
int A[101];
int C[101];
int max(int a, int b)
{
return a>b?a:b;
}
void ZeroOnePack(int cost, int weight, int V)
{
for (int v=V; v>=cost; --v)
F[v] = max(F[v], F[v-cost]+weight);
}
void CompletePack(int cost, int weight, int V)
{
for (int v=cost; v<=V; ++v)
F[v] = max(F[v], F[v-cost]+weight);
}
void MultiPack(int cost, int weight, int V, int amount)
{
if (cost*amount>=V) {
CompletePack(cost, weight, V);
return;
}
int k = 1;
while (k<amount) {
ZeroOnePack(cost*k, weight*k, V);
amount -= k;
k *= 2;
}
ZeroOnePack(cost*amount, weight*amount, V);
}
int main(int argc, char **argv)
{
int n, m, count;
while ((cin>>n>>m) && (m+n)) {
for (int i=1; i<=n; ++i)
cin>>A[i];
for (int i=1; i<=n; ++i)
cin>>C[i];
count = 0;
for (int V=1; V<=m; ++V) {
F[0] = 0;
for (int i=1; i<=m; ++i)
F[i] = MIN_INT;
for (int i=1; i<=n; ++i)
MultiPack(A[i], A[i], V, C[i]);
if (F[V]==V)
++count;
}
cout<<count<<endl;
}
system("pause");
return 0;
}
好吧~POJ的系統說TLE了~悲劇的一米啊~看了discuss說，這題沒那麼簡單O(V*Σlog n[i])是過不了的~好吧，優化優化~
再分析：
其實上面的程序求出了F[V]的值，這個理論上是不需要的，我們關心F[V]是否等於V而已。這裡我們進行優化：
將int F[100001]修改為bool F[100001]，存儲F[V]是否等於V
ZeroOnePack和CompletePack可以修改為
void ZeroOnePack(int cost, int weight, int V)
{
for (int v=V; v>=cost; --v)
F[v] |= F[v-cost];
}
void CompletePack(int cost, int weight, int V)
{
for (int v=cost; v<=V; ++v)
F[v] |= F[v-cost];
}
F[v] |= F[v-cost] 直接或運算用0,1表示此價格是否出現過最後上代碼：
#include <iostream>[cpp] using namespace std;
bool F[100001];
int A[101];
int C[101];
int max(int a, int b)
{
return a>b?a:b;
}
void ZeroOnePack(int cost, int weight, int V)
{
for (int v=V; v>=cost; --v)
F[v] |= F[v-cost];
}
void CompletePack(int cost, int weight, int V)
{
for (int v=cost; v<=V; ++v)
F[v] |= F[v-cost];
}
void MultiPack(int cost, int weight, int V, int amount)
{
if (cost*amount>=V) {
CompletePack(cost, weight, V);
return;
}
int k = 1;
while (k<amount) {
ZeroOnePack(cost*k, weight*k, V);
amount -= k;
k *= 2;
}
ZeroOnePack(cost*amount, weight*amount, V);
}
int main(int argc, char **argv)
{
int n, m;
while ((cin>>n>>m) && (m+n)) {
for (int i=1; i<=n; ++i)
cin>>A[i];
for (int i=1; i<=n; ++i)
cin>>C[i];
F[0] = 1;
for (int i=1; i<=m; ++i)
F[i] = 0;
for (int i=1; i<=n; ++i)
MultiPack(A[i], A[i], m, C[i]);
int ans=0;
for(int i=1;i<=m;++i)
ans+=F[i];
cout<<ans<<endl;
}
system("pause");
return 0;
}
2329MS險過~
using namespace std;
bool F[100001];
int A[101];
int C[101];
int max(int a, int b)
{
return a>b?a:b;
}
void ZeroOnePack(int cost, int weight, int V)
{
for (int v=V; v>=cost; --v)
F[v] |= F[v-cost];
}
void CompletePack(int cost, int weight, int V)
{
for (int v=cost; v<=V; ++v)
F[v] |= F[v-cost];
}
void MultiPack(int cost, int weight, int V, int amount)
{
if (cost*amount>=V) {
CompletePack(cost, weight, V);
return;
}
int k = 1;
while (k<amount) {
ZeroOnePack(cost*k, weight*k, V);
amount -= k;
k *= 2;
}
ZeroOnePack(cost*amount, weight*amount, V);
}
int main(int argc, char **argv)
{
int n, m;
while ((cin>>n>>m) && (m+n)) {
for (int i=1; i<=n; ++i)
cin>>A[i];
for (int i=1; i<=n; ++i)
cin>>C[i];
F[0] = 1;
for (int i=1; i<=m; ++i)
F[i] = 0;
for (int i=1; i<=n; ++i)
MultiPack(A[i], A[i], m, C[i]);
int ans=0;
for(int i=1;i<=m;++i)
ans+=F[i];
cout<<ans<<endl;
}
system("pause");
return 0;
}
2329MS險過~
