poj 2642 The Brick Stops Here(二维0/1背包)

点击打开链接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;
}