P1048 [NOIP2005 普及组] 采药
一道dp背包的模板题 但我也还是不怎么理解
输入输出样例
输入 #1
70 3 71 100 69 1 1 2
输出 #1
3
代码如下
思路的话就和dp背包的是一样的，每种草药都有拿或者不拿的两种状态
二维数组：
#include<bits/stdc++.h>
using namespace std;
int w[101],val[101]//w为重量（时间），val为价值
int dp[1001][1001];//dp数组二维是时间，一维是药草编号（假定）
int main(){int t,m;cin>>t>>m;for(int i=1;i<=m;i++){cin>>w[i]>>val[i];}for(int i=1;i<=m;i++)//药草编号 for(int j=1;j<=t;j-++){ if(j<w[i]){
//dp[i][j]以j为容量为放入前i个物品(按i从小到大的顺序)的最大价值dp[i][j]=dp[i-1][j]; //不拿}else{dp[i][j]=max(dp[i-1][j],dp[i-1][j-w[i]]+val[i]);//拿，但要选大的拿
//样例给的70采药时间，从1~70每个数据都可能会有用，这个要根据m组里面的数据来定，就拿dp[3][70]来说
//dp[3][70]=max(dp[2][70],dp[2][1(70-69)]+1);而dp[2][1]=max(dp[1][1],dp[1][1-1]+1);
//这样dp[3][70]刚好取到了所能取到的最大值
//这样一看 便用到了前面很多的数据 最好画个图模拟一下这个过程233，我也不知道该怎么说（我也不怎么明白qaq）大概就是确定了方程然后进行递推的一个过程}}cout<<dp[m][t];
} 一维数组：
#include<iostream>
using namespace std;
int dp[1001],w[1001],val[1001];
int main(){int t,m;cin>>t>>m;for(int i=1;i<=m;i++){cin>>w[i]>>val[i];} for(int i=1;i<=m;i++)//i代表的是组数for(int j=t;j>=0;j--){//j代表时间 j>=0也可改为j>=w[i]if(j>=w[i]){dp[j]=max(dp[j-w[i]]+val[i],dp[j]);}}cout<<dp[t];
//最后一位是最大值的原因是在外循环还是第一层的时候就会发现 //其实在数组里面dp[t]就是最大值了 因为它代表的是最大的空间 如果最大的空间的值即dp【t】为0 //那么下面的一定也都为零//原理很简单 t个空间都装不下的东西 小于t的能装下来吗？
}记录一下 方便日后回看