DP(五)——簡單的多重背包
POJ 1014 http://poj.org/problem?id=1014
題意是這樣的:有分別價值為1,2,3,4,5,6的6種物品,輸入6個數字,
表示相應價值的物品的數量,問一下能不能將物品分成兩份,
是兩份的總價值相等,其中一個物品不能切開,只能分給其中的某一方,
當輸入六個0是(即沒有物品了),這程序結束,總物品的總個數不超過20000
Sample Input
1 0 1 2 0 0
1 0 0 0 1 1
0 0 0 0 0 0
Sample Output
Collection #1:
Can't be divided.
Collection #2:
Can be divided.
下面一個是個高效的算法,但是不是最高的。
View Code
#include<iostream> using namespace std; #define size 70010 int f[2*size]; int a[10]; int MultP(int n, int v){ int i, j, k, amount; memset(f, 0, sizeof(f)); for(i=1; i<=n; i++){ //枚舉物品的總數量,(這里數量=價值) if(a[i]*i>=v){ //完全背包,(a[i]表示第i件物品的數量) for(j=i; j<=v; j++) f[j] = max(f[j], f[j-i]+i); } else{ //01背包 k=1; amount = a[i]; while(k<amount){ for(j=v; j>=k*i; j--) f[j] = max(f[j], f[j-k*i]+k*i); amount -= k; k = k*2; } for(j=v; j>=amount*i; j--) f[j] = max(f[j], f[j-amount*i]+amount*i); } } return f[v]; } int main() { int Case=0, flag, i, sum; while(1) { Case++; sum = 0; for(i=1; i<=6; i++) { cin>>a[i]; sum+=a[i]*i; } flag = 0; for(i=1; i<7; i++) { if(a[i]!=0) { flag = 1; break; } } if(flag == 0) break; if(sum%2==1) { cout<<"Collection #"<<Case<<":"<<endl<<"Can't be divided."<<endl<<endl; continue; } i = MultP(6, sum/2); if(i==(sum/2)) cout<<"Collection #"<<Case<<":"<<endl<<"Can be divided."<<endl<<endl; else cout<<"Collection #"<<Case<<":"<<endl<<"Can't be divided."<<endl<<endl; } }
下面給出一個不是很高效的算法,在POJ上是超時的。
View Code
#include<iostream>
using namespace std;
#define size 20005
int num[7];
bool f[size];
int main()
{
int ex = 0, sum, i, j, k, Max, t, flag;
while(cin>>num[0]>>num[1]>>num[2]>>num[3]>>num[4]>>num[5])
{
ex++;
sum=0, flag=0;
for(i=0; i<6; i++) sum+=num[i]*(i+1);
if(sum==0) break;
if(sum%2==1)
{
cout<<"Collection #"<<ex<<":"<<endl<<"Can't be divided."<<endl<<endl;
continue;
}
//接下來多重背包
Max = 0;
f[0] = true; //這個是初始化問題
for(i=0; i<6; i++) //枚舉每件物品
{
for(k=Max; k>=0; k--) //01背包的做法
{
if(f[k]==true) //判斷此時f[k]是否已經存在,只有存在了,才可以繼續DP
{
for(j=1; j<=num[i]; j++) //件數,從1開始
{
t = k+j*(i+1); //此時的價值
f[t] = true;
if(t>Max) Max = t;
if(Max==(sum/2))
{
flag = 1;
break;
}
}
}
if(flag) break;
}
if(flag) break;
}
if(flag) cout<<"Collection #"<<ex<<":"<<endl<<"Can be divided."<<endl<<endl;
else cout<<"Collection #"<<ex<<":"<<endl<<"Can't be divided."<<endl<<endl;
}
}
posted on 2011-11-16 21:40 More study needed. 閱讀(272) 評論(0) 收藏 舉報

浙公網安備 33010602011771號