首页 > 代码库 > 台州 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 多重背包
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。