poj 2642 The Brick Stops Here(2 D 0/1リュックサック)

クリックしてリンクpoj 2642を開く
構想:0/1リュックサック分析:1テーマはn個の物品を与え、しかも各物品は2種類の選択しかなく、明らかに0/1リュックサックの特性である.2題c個の顧客の要求を与え、各顧客は最後の金の平均濃度がmin~maxという区間であることを要求し、各顧客はm個の物品3を要求し、我々は顧客がm個の物品の総濃度がm*min~m*maxという区間であることを選択したと考えることができる.ではdp[i][j][k]=min(dp[i-1][k][j],dp[i-1][k-1][j-v[i]+w[i]);3 Dの複雑さのため,我々は次元を下げる必要があり,リュックサックの次元を下げるには逆順列挙によって得られる.
コード:

#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
" , ans);
    }
    return 0;
}