点击打开链接poj 2642
思路: 0/1背包
分析:
1 题目给定n个物品,并且每个物品只有两种的选择很明显就是0/1背包的特性。
2 题目给定c个客户的要求,每一个客户都要求最后金子的平均浓度在min~max这个区间,并且每个客户要m个物品
3 我们可以认为是客户选取了m个物品总的浓度在m*min~m*max这个区间,那么我们定义dp[i][k][j]表示前i个物品选k个放入浓度为j的背包,那么dp[i][j][k] = min(dp[i-1][k][j] , dp[i-1][k-1][j-v[i]]+w[i]);由于三维的复杂度很大,我们必须要进行降维,对于背包的降维来说都是通过逆序枚举得到
代码:
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
const int INF = 0x3f3f3f3f;
const int N = 25;
const int MAX = 210;
const int MAXN = 1010*N;
int n , c , m , minV , maxV;
int v[MAX] , w[MAX] , dp[N][MAXN];
void solve(){
memset(dp , INF , sizeof(dp));
dp[0][0] = 0;
for(int i = 1 ; i <= n ; i++){
for(int k = N-1 ; k >= 1 ; k--){
for(int j = MAXN-1 ; j >= v[i] ; j--)
dp[k][j] = min(dp[k][j] , dp[k-1][j-v[i]]+w[i]);
}
}
}
int main(){
scanf("%d" , &n);
for(int i = 1 ; i <= n ; i++)
scanf("%d%d" , &v[i] , &w[i]);
solve();
scanf("%d" , &c);
while(c--){
scanf("%d%d%d" , &m , &minV , &maxV);
int ans = INF;
for(int k = m*minV ; k <= m*maxV ; k++)
ans = min(ans , dp[m][k]);
if(ans == INF)
puts("impossible");
else
printf("%d\n" , ans);
}
return 0;
}
分享到:
相关推荐
poj 1611 The Suspects 代码 并查集的应用
晒代码之二——多重背包(POJ1276)
北大POJ1027-The Same Game 解题报告+AC代码
北大POJ1426-Find The Multiple【BFS+同余模】 解题报告+AC代码
北大POJ1163-The Triangle 解题报告+AC代码
北大POJ1163-The Triangle
POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类
poj 1611 The Suspects.md
先利用prim算法求出最小生成树,然后通过往MST里加边来判断新生成的最小生成树是否具有最小的权值,POJ上The Unique MST(1679)题是要求判断最小生成树是否唯一,此题其实根本不用这样做,但是为了练习球次小生成树...
poj 3191 The Moronic Cowmpouter.md
poj 1989 The Cow Lineup.md
poj 3260 The Fewest Coins.md
poj 3901 The Computer Game.md
NULL 博文链接:https://128kj.iteye.com/blog/1747400
北大POJ1207-The 3n + 1 problem 解题报告+AC代码
北大POJ2151-Check the difficulty of problems 解题报告+AC代码
北大POJ1014-Dividing【DFS】【多重背包+二进制优化】 解题报告+AC代码
poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题...
NULL 博文链接:https://128kj.iteye.com/blog/1746750
<1> 0-1背包,经典问题 无限背包,经典问题 判定性背包问题 带附属关系的背包问题 <5> + -1背包问题 双背包求最优值 构造三角形问题 带上下界限制的背包问题(012背包) 3.线性的动态规划问题 <1>积木游戏...