当前位置: 代码迷 >> 综合 >> JakeLin-[ACM训练]采药-DP/01背包-题解
  详细解决方案

JakeLin-[ACM训练]采药-DP/01背包-题解

热度:65   发布时间:2023-11-13 15:23:42.0

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

输入

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

输出

输出一行,这一行只包含一个整数,表示在规定的时间内,可以采到的草药的最大总价值。

样例输入

70 3
71 100
69 1
1 2

样例输出

3

原题链接:采药

一、 0/1背包动态规划的思想就是:

眼前到了这第 i 棵药,我有两种选择
1.我要采它:若我采了它,那么我所拥有的时间会减少,而我所获得的价值会增加
2.我不采它:若我不采它,那么我的时间不会减少,价值也不会增加,还保留在i-1步的价值


二、我们约定俗成的设计了一个DP数组int dp[maxn][maxn2];,其原理非常重要:
dp[i][j]表示的值是什么?是这个状态的最大value值!什么状态?是在考虑第i个物品(前i-1个已经安排好了),花费时间为j的这么一个状态下,最大值value。
所以我们是不是可以这样认为:整个程序其实就是在构造一个dp数组,它可以把 [第几个物品] - [剩余时多少] - [总价值多少] 这三个要素归纳成一个状态,终点就是dp[所有物品][所有时间]


回到一,继续分析两种情况:

1、分析第i个物品

那么就是要确定dp[i][*],此时cost[i]、value[i]表示第i个物品的花费和时间

2、再分析剩余时间的情况j

  • 如果剩余时间都比cost[i]都小,那肯定采不了,没时间呀。
  • 如果我的时间够采i,那我要考虑考虑了:
    • 如果我采它,它构成了一种新的状态,我剩的时间减少了cost[i],而价值是增加value[i]:dp[i][j]->dp[i-1][j-cost[i]]+value[i]
    • 如果我不采,我既不花费时间,也不增长价值,状态dp[i][j]和dp[i-1][j]是一样
#include<cstdio>
#include<iostream>
#include<algorithm>
using namespace std;
const int maxn = 100 + 10;
const int maxn2 = 1000 + 10; 
int cost[maxn];
int value[maxn];
int dp[maxn][maxn2];
int main(){int n,m;cin>>n>>m;for(int i=1;i<=m;i++){cin>>cost[i]>>value[i];}for(int i=1;i<=m;i++){  //第i个物品(药)是否放入背包(采它) for(int j=1;j<=n;j++){  // 遍历可能的时间情况 if(j>=cost[i]){  //max(采,不采) dp[i][j] = max(dp[i-1][j-cost[i]]+value[i],dp[i-1][j]);}else{  //cost[i]:采第i个药要花的时间,如果j不够肯定采不了 dp[i][j] = dp[i-1][j];    }}}cout<<dp[m][n];return 0;
}

 后续优化,将dp数组去掉一维,少了表示i(i个药)的维数,[自底向上]地构造dp数组:

#include<cstdio>
#include<iostream>
#include<algorithm>
using namespace std;
const int maxn = 110;
const int tmaxn = 1010;
int cost[maxn],value[maxn];
int dp[tmaxn];
int main(){int t,m;cin>>t>>m;for(int i=1;i<=m;i++){cin>>cost[i]>>value[i];}for(int i=1;i<=m;i++){for(int j=t;j>=cost[i];j--){dp[j] = max(dp[j],dp[j-cost[i]]+value[i]);}}cout<<dp[t];return 0;
}

 

以上就是使用两种DP算法解决0/1背包的问题。