背包问题

整理自杭州电子科大刘春英老师PPT及《背包九讲》崔天翼

问题模型

给你一个容量为V的背包和若干种物品，在一定的限制条件下（每种物品都占用一定容量），问最多能放进多少价值的物品？

和动态规划的联系：背包的每个容量就是“状态”,选择每个物品就是“状态的决策”。

01 背包

问题描述

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

问题特点

每种物品仅有一件，可以选择放或不放，用子问题定义状态：即f[i][v]表示前i件物品恰放入一个容量为v的背包可以获得的最大价值。

状态转移方程

(f[i][v]=max{f[i-1][v],f[i-1][v-c[i]]+w[i]})

完全背包

问题描述

有N种物品和一个容量为V的背包，每种物品都有无限件可用。第i种物品的费用是c[i]，价值是w[i]。求解将哪些物品装入背包可使这些物品的费用总和不超过背包容量，且价值总和最大。

问题特点

按照01思路的想法，策略从取或者不取变成每种取多少个

状态转移方程

(f[i][v]=max{f[i-1][v-kc[i]]+kw[i] | 0ge kc[i]le v})

多重背包

问题描述

有 N 种物品和一个容量为 V 的背包。第 i 种物品最多有 M i 件可用,每件耗费的
空间是 (C_i) ,价值是 (W_i) 。求解将哪些物品装入背包可使这些物品的耗费的空间总和不超
过背包容量,且价值总和最大。

例题

(HDU 2602) The bone collector had a big bag with a volume of V ,and along his trip of collecting there are a lot of bones , obviously , different bone has different value and different volume, now given the each bone’s value along his trip , can you calculate out the maximum of the total value the bone collector can get ?

#include <iostream>
#include <cstring>
#define maxn 1010

using namespace std;
int volume[maxn]={0};
int value[maxn]={0};
int dp[maxn]={0};
int main(){
    int t,n,v,i,j;
    cin >> t;
    while(t--){
        memset(volume,0,sizeof(volume));
        memset(value,0,sizeof(value));
        memset(dp,0,sizeof(dp));
        cin >> n >> v;
        for(i=0;i<n;i++)
            cin >> value[i];
        for(i=0;i<n;i++)
            cin >> volume[i];
        if(n==0 || v==0){
            cout <<  '0'<< endl;
            continue;
        }
        for(i=0;i<n;i++){
            for(j=v;j>=volume[i];j--){
                dp[j] = max(dp[j],dp[j-volume[i]]+value[i]);
            }
        }
         cout << dp[v] << endl;
    }   
}

(HDU1248) 我们这里有三种道具,血瓶150块一个,魔法药200块一个,无敌药水350块一个." 共有N元，求结余最少；

#include <iostream>
#include <cstring>
#define maxn 10001

using namespace std;

int cost[3]={150,200,350};
int value[3]={150,200,350};
int dp[maxn]={0};
int main(){
    int t,n,i,j,out=0;
    cin >> t;
    while(t--){
        out = 0;
        memset(dp,0,sizeof(dp));
        cin >> n;
        if(n<150){
            cout << n << endl;
            continue;
        }   
        for(i=0;i<3;i++){
            for(j=0;j<=n;j++){
                if(j>=cost[i]){
                    dp[j] = max(dp[j],dp[j-cost[i]]+value[i]);
                    out = max(out,dp[j]);
                }
            }
        }
        cout << n-out << endl;       
    }
}

(HDU2191)急！灾区的食物依然短缺！
为了挽救灾区同胞的生命，心系灾区同胞的你准备自己采购一些粮食支援灾区，现在假设你一共有资金n元，而市场有m种大米，每种大米都是袋装产品，其价格不等，并且只能整袋购买。
请问：你用有限的资金最多能采购多少公斤粮食呢？

思路一：转化为01背包问题，把所有的物品都作为候选项，判断这个物体是否放；简单直观；

#include <iostream>
#include <cstring>

using namespace std;

struct rice{
    int p;
    int h;
    int c;
}rices[2001];

int c,n,m,num,i,j;
int dp[2001]={0};
int main(){
    cin >> c;
    while(c--){
        memset(dp,0,sizeof(dp));
        memset(rices,0,sizeof(rices));
        cin >> n >> m;
        for (i=0,j=0;i<m;i++,j++){
            cin >> rices[j].p;
            cin >> rices[j].h;
            cin >> num;
            for (int k=0;k<num-1;k++){
                rices[k+1+j].p = rices[j].p;
                rices[k+1+j].h = rices[j].h;
            }
            j += num-1;
        }
        num = j;
        int maxo = 0;
        for(int i=0;i<num;i++){
            for(int j=n;j>=rices[i].p;j--){
                dp[j] = max(dp[j],dp[j-rices[i].p]+rices[i].h);
                //maxo = max(maxo,dp[j]);
            }
        }
        cout << dp[n] << endl;
    }
}