动态规划详解（C++版）

输出格式：

输出文件只有一个正整数，为不超过总钱数的物品的价格与重要度乘积的总和的最大值 （<200000）。 样例输入： 1000 5 800 2 0 400 5 1 300 5 1 400 3 0 500 2 0 样例输出： 2200 分析：

这是一道“有依赖的背包问题”。将主、附件压成物品组，然后对新编好的组进行01背包。记住状态有5种：啥都不选、选主件、主件+附件1、主件+附件2、主件+附件1+附件2。 参考程序：

#include #include #include using namespace std; int n,m;

int w[61][4],v[61][6],num[61]; int f[32001]; int x,y,z; int main() {

scanf(\ for(int i=1;i<=m;i++) {

scanf(\ if(z==0) {

w[i][0]=x/10; v[i][0]=x*y/10; } else {

num[z]++;

w[z][num[z]]=x/10; v[z][num[z]]=y*x/10; } }

for(int i=1;i<=m;i++)

for(int j=n;j>=w[i][0];j--) {

if(w[i][0]==0) break;

f[j]=max(f[j],f[j-w[i][0]]+v[i][0]);//选主件 if(j-w[i][0]-w[i][1]>=0)

f[j]=max(f[j],f[j-w[i][0]-w[i][1]]+v[i][0]+v[i][1]);//加第一个附件 if(j-w[i][0]-w[i][2]>=0)

f[j]=max(f[j],f[j-w[i][0]-w[i][2]]+v[i][0]+v[i][2]);//加第二个附件 if(j-w[i][0]-w[i][1]-w[i][2]>=0)

f[j]=max(f[j],f[j-w[i][0]-w[i][1]-w[i][2]]+v[i][0]+v[i][1]+v[i][2]);//两个一起加 }

printf(\}

5． 藐视猪仙（TYVJ1549） 问题描述：

猪仙最恨几何题??于是魂之挽歌给他弄了一堆几何题做??

猪仙做每道题都需要一定的时间t[i]，如果他开始做某题，那么一定会把它做完，如果猪仙没有做某题的话，魂之挽歌会藐视他，藐视度为x[i]为了更多的藐视猪仙，魂之挽歌不会把所有的时间都让猪仙去做题的，所以每道题魂之挽歌会在a[i]时刻发给猪仙，也就是说a[i]时刻之前猪仙不能做第i道题。猪仙一共有T的时间，他希望总藐视度最小。 输入格式 ：

第一行两个正整数T，N(T<=10000,N<=100)。 接下来有n行，每行三个数a[i],t[i],x[i] a[i]<=T,t[i]<=T,x[i]<=2000 输出格式：

仅一个正整数，表示最小藐视度。 样例输入： 5 3 1 1 2 1 3 5 4 1 3

样例输出： 0

分析：

就是简单的01背包,用s记录总的藐视度，f[i]表示i时间内能得到的最高的藐视度，最后用s-f[t]就可以了。但是要注意一点，样例中第一时刻发了第一道题，意思就是第一时刻已经有了这题，而这道题只用一个时间，所以第一时刻就可以做完这题了。 所以样例输出应该是0 参考程序：

#include #include #include using namespace std; int n,m;

int a[10001],t[10001],x[10001],f[10001]={0},d[10001]; int s,i,j; int main() {

s=0;