首页 > 代码库 > 台州 OJ 1315 Dividing 多重背包

台州 OJ 1315 Dividing 多重背包

题目的大概意思就是,有 6 种石头,价值分别是 1,2,3,4,5,6,给出他们的数量,求是否能将他们平分成两组价值相同的石头。

设石头的总价值为sum。把石头的价值看成重量,则问题转换成是否能恰好装下指定重量的石头,及背包容量为 sum/2 时,是否存在恰好装下一些石头的情况。

代码:

#include <iostream>
#include <cstring>
using namespace std;

const int MAX = 120005;

int dp[MAX];
int num[7];

//多重背包问题,背包的重量为 i,不考虑价值,只考虑是指定重量(所有重量的一半)可否到达。 
//写出框架,再考虑剪枝 
int main(){
    //freopen("input.txt", "r", stdin);
    int T = 0;
    while(1){
        bool isEnd = true;
        int sum = 0;
        for(int i=1; i<=6; i++){
            cin >> num[i];
            sum += i*num[i];
            if(num[i])
                isEnd = false;
        }
        if(isEnd){
            break;
        }
        
        cout << "Collection #" << ++T << ":" << endl;
        
        if(sum & 1){        //奇数不可能平分 
            cout << "Can‘t be divided." << endl << endl;
            continue;
        }
        
        sum /= 2;
        memset(dp, 0, sizeof(dp));
        dp[0] = 1;        //初始状态,其他价值设为不可到达 
        int maxValue = http://www.mamicode.com/0;    //可到达的最大价值 
        
        //DP
        for(int i=1; i<=6; i++){ 
            for(int j=maxValue; j>=0; j--){    
                if(num[i] && dp[j]){    //如果前一个物品的 j 可到达,则从前一个物品在 j 的状态转移过来  
                    for(int k=1; k<=num[i]; k++){    //从 j 状态出发,将所有可到达的状态标记 
                        if(dp[j+k*i] == 1)            //后面的状态一定已经标记过了,因为 j 是递减的。 
                            break;
                        dp[j+k*i] = 1;
                    }
                }
            }
            maxValue += i*num[i];    //可到达的最大价值增加
            if(maxValue >= sum)
                maxValue = sum;        //最大到目标价值就可以了,比目标价值大的不用考虑 
        }
        
        if(dp[sum]){
            cout << "Can be divided." << endl << endl;
        }else{
            cout << "Can‘t be divided." << endl << endl;
        }
    }
} 

 

台州 OJ 1315 Dividing 多重背包