29 背包问题

理论说明

本节将要讨论动态规划问题中又一个十分常见，同时在机试中又是终点被考察的问题--背包问题。背包问题的变化之多让我们不容易一下子完全掌握它，根据考研机试的实际需要，我们在本节中主要讨论0-1背包、完全背包和多重背包这三类背包问题。

题目来源

2008年北京大学图形学实验室计算机研究生机试真题

题目描述

辰辰是个很有潜能、天资聪颖的孩子，他的梦想是称为世界上最伟大的医师。 为此，他想拜附近最有威望的医师为师。医师为了判断他的资质，给他出了一个难题。 医师把他带到个到处都是草药的山洞里对他说： “孩子，这个山洞里有一些不同的草药，采每一株都需要一些时间，每一株也有它自身的价值。 我会给你一段时间，在这段时间里，你可以采到一些草药。如果你是一个聪明的孩子，你应该可以让采到的草药的总价值最大。” 如果你是辰辰，你能完成这个任务吗？

输入说明

输入的第一行有两个整数T（1 <= T <= 1000）和M（1 <= M <= 100），T代表总共能够用来采药的时间，M代表山洞里的草药的数目。 接下来的M行每行包括两个在1到100之间（包括1和100）的的整数，分别表示采摘某株草药的时间和这株草药的价值。

输出说明

可能有多组测试数据，对于每组数据， 输出只包括一行，这一行只包含一个整数，表示在规定的时间内，可以采到的草药的最大总价值。

样例展示

输入：
70 3
71 100
69 1
1 2
输出：
3

题目分析

我们可以将这个问题抽象：有一个容量为V的背包，和一些问题。这些物品分别有两个属性，体积w和价值v,每种物品只有一个。要求这个背包装下价值尽可能多的物品，求该最大价值，背包可以不被装满。

因为最优解中，每个物品都有两种可能的情况，即在背包中或者不在背包中，所以我们将这个问题称为0-1背包问题。

在众多方案中求解最优解，是典型的动态规划问题。为了用动态规划来解决该问题，我们用dp[i][j]表示在总体积不超过j的情况下，前i个物品所能达到的最大价值。初始时,dp[0][j]为0.依据每种物品是否被放入背包，每个状态有两个状态转移的来源。若物品i被放入背包中，设其体积为w,价值为v,则dp[i][j]=dp[i-1][j-w]+v。即在总体积不超过j-w时前i-1件物品可组成的最大价值的基础上再加上i物品的价值v；若物品i不被放入背包中，则dp[i][j]=dp[i-1][j],即此时与总体积不超过j的钱i-1件物品组成的价值最大值等价。选择他们之间的最大值称为状态dp[i][j]的值。综上所述，0-1背包的状态转移方程为：

  dp[i][j]=max(dp[i-1][j-w]+v,dp[i-1][j]);
  注意：j-w的值是否为负数，若为负，则不能转移

C++代码

#include<iostream>
using namespace std;

int max(int a,int b) {
    return a>b? a:b;
}

struct E{
    int w;
    int v;
}list[101];

int dp[101][101];
int s,n;
int main() {
    //dp[i][j]表示在总体积不超过j的情况下，前i个物品所能达到的最大价值。
    while(scanf("%d%d",&s,&n)!=EOF) {
        for(int i=1;i<=n;i++) {
            scanf("%d%d",&list[i].w,&list[i].v);
        }
        for(int i=0;i<=s;i++) {
            dp[0][i]=0;
        }
        for(int i=1;i<=n;i++) { //玄幻每一个物品
            for(int j=s;j>=list[i].w;j--) { //确保j-list[i]>=0
                dp[i][j]=max(dp[i-1][j],dp[i-1][j-list[i].w]+list[i].v);
            }
            for(int j=list[i].w-1;j>=0;j--) {
                dp[i][j]=dp[i-1][j];
            }
        }
        printf("%d",dp[n][s]);
    }
    return 0;
}

后续分析

观察状态转移的特点，我们发现dp[i][j]的转移仅仅与dp[i-1][j-list[i].w]和dp[i-1][j]有关，即仅仅与二维数组中本行的上一行有关。根据这个特点，我们将原来的二维数组优化成一维数组，并用如下方式完成状态转移：

dp[j]=max{dp[j-list[i].w]+v,dp[j]}

其中再本次跟新中未经修改的dp[j-list[i].w]和dp[j]与原始写法中的dp[i-1][j-list[i].w]和dp[i-1][j]等值。为了保证状态正确的转移，我们必须保证再每次跟新中确定状态dp[j]时，dp[j]和dp[j-list[i].w]未被本次跟新修改，考虑到j-list[i].w<j，那么在每次跟新中倒序遍历所有j的值，就能保证在确定dp[j]的值时，dp[j-list[i].w]的值尚未被修改，从而完成正确的状态转移

#include<iostream>
using namespace std;
#define INF 0x7fffffff

int max(int a,int b) {
    return a>b? a:b;
}

struct E {
    int w;
    int v;
}list[100];

int dp[1001];
int main() {
    int s,n;
    while(scanf("%d%d",&s,&n)!=EOF) {
        for(int i=1;i<=n;i++) {
            scanf("%d%d",&list[i].w,&list[i].v);
        }
        for(int i=0;i<=s;i++) {
            dp[i]=0;
        }
        for(int i=1;i<=n;i++) {
            for(int j=s;j>=list[i].w;j--) {
                dp[j]=max(dp[j],dp[j-list[i].w]+list[i].v);
            }
        }
        printf("%d\n",dp[s]);
    }
    return 0;
}

Piggy-Bank

题目描述

输入说明

输出说明

样例说明

问题分析

题目大意：有一个存储罐，告知为空时的重量和当前重量，并给定一些钱币的价值和相应的重量，求存储罐中最少有多少先进。