完全なリュックサックのテーマ:

pku 1384 Piggy-Bank完全リュックサック入門テーマ. 
http://poj.org/problem?id=1384
ここはただ求めているのがちょうどいっぱいで、しかも最小です.ちょうど満タンになったときにf[0]=0を与えるだけです.他の1つの未定義状態は負が無限で正が無限であればよい.


View Code

#include <iostream>

#include <cstdio>

#include <cstring>

#include <algorithm>

#include <cmath>

#include <queue>

#include <stack>

#include <set>

#include <map>

#include <string>



#define CL(a,num) memset((a),(num),sizeof(a))

#define iabs(x)  ((x) > 0 ? (x) : -(x))

#define Min(a , b) ((a) < (b) ? (a) : (b))

#define Max(a , b) ((a) > (b) ? (a) : (b))



#define ll __int64

#define inf 0x7f7f7f7f

#define MOD 100000007

#define lc l,m,rt<<1

#define rc m + 1,r,rt<<1|1

#define pi acos(-1.0)

#define test puts("<------------------->")

#define maxn 100007

#define M 10007

#define N 504

using namespace std;

//freopen("din.txt","r",stdin);



int f[M],w[N],c[N];



int main(){

    //freopen("din.txt","r",stdin);

    int n,m;

    int T,i,j;

    scanf("%d",&T);

    while (T--){

        scanf("%d%d",&n,&m);

        int V = m - n;

        scanf("%d",&n);

        for (i = 0; i < n; ++i){

            scanf("%d%d",&w[i],&c[i]);

        }



        for (i = 0; i < M; ++i) f[i] = inf;

        f[0] = 0;



        for (i = 0; i < n; ++i){

            for (j = c[i]; j <= 10000; ++j){

                f[j] = min(f[j],f[j - c[i]] + w[i]);

            }

        }

        if (f[V] != inf) printf("The minimum amount of money in the piggy-bank is %d.
",f[V]);

        else printf("This is impossible.
");

    }

    return 0;

}

 
pku 2063 Investmentマルチフルバックパック
http://poj.org/problem?id=2063
タイトル:
初期金銭数を与え、d種類の債券の利益c[i]を与え、w[i]は毎年c[i]の債券を買うとw[i]の利益を得ることができる.あなたの使用年mを与えて、最初に与えられたお金の数を利用して最後に得た最大の総金額を聞いてください.
考え方
利益を物品のw値と見なし、債券の金額を物品の費用と見なす.リュックサックの容量が初期金額のリュックサックに物を入れて得られる最大値(最大利益)を求めます.


View Code

#include <iostream>

#include <cstdio>

#include <cstring>

#include <algorithm>

#include <cmath>

#include <queue>

#include <stack>

#include <set>

#include <map>

#include <string>



#define CL(a,num) memset((a),(num),sizeof(a))

#define iabs(x)  ((x) > 0 ? (x) : -(x))

#define Min(a , b) ((a) < (b) ? (a) : (b))

#define Max(a , b) ((a) > (b) ? (a) : (b))



#define ll __int64

#define inf 0x7f7f7f7f

#define MOD 100000007

#define lc l,m,rt<<1

#define rc m + 1,r,rt<<1|1

#define pi acos(-1.0)

#define test puts("<------------------->")

#define maxn 100007

#define M 100007

#define N 17

using namespace std;

//freopen("din.txt","r",stdin);



int f[M];

int c[N],w[N];



int main(){

    //freopen("din.txt","r",stdin);

    int i,j,T,d;

    int n,m;

    scanf("%d",&T);

    while (T--){

        scanf("%d%d",&n,&m);

        scanf("%d",&d);

        for (i = 1; i <= d; ++i){

            scanf("%d%d",&c[i],&w[i]);

            c[i] /= 1000;

        }

        while (m--){

            for (i = 0; i < M; ++i) f[i] = 0;

            int tmp = n/1000;

            for (i = 1; i <= d; ++i){

                for (j = c[i]; j <= tmp; ++j){

                    f[j] = max(f[j],f[j - c[i]] + w[i]);

                }

            }

            n += f[tmp];

        }

        printf("%d
",n);

    }

    return 0;

}

 
 
更新待ち...