背包问题

1. 01背包

问题描述：

小Ho现在手上有M张奖券，而奖品区有N件奖品，分别标号为1到N，其中第i件奖品需要need(i)张奖券进行兑换，同时也只能兑换一次。为了使得辛苦得到的奖券不白白浪费，小Ho给每件奖品都评了分，其中第i件奖品的评分值为value(i),表示他对这件奖品的喜好值。现在他想知道，凭借他手上的这些奖券，可以换到哪些奖品，使得这些奖品的喜好值之和能够最大。

#include<stdio.h>
#include<string.h>
#define M 100005
int V[M];

int main()
{
    int n, m, need, value, i, j;
    scanf("%d%d", &n, &m);
    for (i = 0; i < n; i++)
    {
        scanf("%d%d", &need, &value);
        for (j = m; j >= need; j--)  //逆向
        {
            if (V[j - need] + value>V[j])
                V[j] = V[j - need] + value;
        }
    }
    printf("%d
", V[m]);
    return 0;
}

2. 完全背包

问题描述：

小Ho现在手上有M张奖券，而奖品区有N种奖品，分别标号为1到N，其中第i种奖品需要need(i)张奖券进行兑换，并且可以兑换无数次，为了使得辛苦得到的奖券不白白浪费，小Ho给每件奖品都评了分，其中第i件奖品的评分值为value(i),表示他对这件奖品的喜好值。现在他想知道，凭借他手上的这些奖券，可以换到哪些奖品，使得这些奖品的喜好值之和能够最大。

#include<stdio.h>
#include<string.h>
#define M 100005
int V[M];

int main()
{
    int n, m, need, value, i, j;
    scanf("%d%d", &n, &m);
    for (i = 0; i < n; i++)
    {
        scanf("%d%d", &need, &value);
        for (j = need; j <=m; j++) //正向
        {
            if (V[j - need] + value>V[j])
                V[j] = V[j - need] + value;
        }
    }
    printf("%d
", V[m]);
    return 0;
}

3. 多重背包

http://blog.csdn.net/insistgogo/article/details/11176693

有N种物品和一个容量为V的背包。第i种物品最多有num[i]件可用，每件费用是c[i]，价值是w[i]。求解将哪些物品装

入背包可使这些物品的费用总和不超过背包容量，且价值总和最大。 

例：

http://hihocoder.com/problemset/problem/1364

可以转化为多重背包。用0-1背包做会超时。

#include <iostream>
#include <vector>
#include <map>
using namespace std;

map<pair<int, int>, int> cnt;

int main()
{
    int n, m, w, p, num;
    cin >> n >> m;
    for (int i = 0; i < n; i++)
    {
        cin >> w >> p;
        cnt[make_pair(w, p)]++;
    }
    vector<pair<int, int>> v;
    for (map<pair<int, int>, int>::iterator it = cnt.begin(); it != cnt.end(); it++)
    {
        w = it->first.first;
        p = it->first.second;
        num = it->second;
        for (int k = 1; num; k <<= 1)
        {
            if (k <= num)
            {
                v.push_back(make_pair(w*k, p*k));
                num -= k;
            }
            else
            {
                v.push_back(make_pair(w*num, p*num));
                num = 0;
            }
        }
    }
    vector<int> pr(m + 1, 0);
    for (int l = v.size(), i = 0; i < l; i++)
    {
        w = v[i].first;
        p = v[i].second;
        for (int j = m; j >= w; j--)
            pr[j] = max(pr[j], pr[j - w] + p);
    }
    cout << pr[m] << endl;

    return 0;
}