大家好,这次给大家分享的题会比以往难一点,
学会了这道题的解题思想,对动态规划的掌握
就更上一层楼了
给定n种物品和一背包。物品i的重量是wi,其价值为vi,背包的容量为C。问应如何选择装入背包的物品,使得装 入背包中物品的总价值最大?
个人感觉这道经典的0-1背包问题还是挺难的,
反正当时看了好几遍才看懂,才理解它的做法
当然,对于这道题,如果你想要暴力递归的方法做也是可以的。例如我们可以把所有物品看出一个集合,然后把所有子集都求出来,然后看看那个集合的物品装的下且价值最高。不过时间复杂度是2的n次方。指数增长的复杂度自己掂量。
大家可以尝试用下把solve(i,j)这个函数是否算过的状态保存起来,然后计算之前先查看是否已经算过。如果算过则直接返回。递归式的动态规划就不带大家做了,主要是多接触下其他做法勒,题就要多做才能熟能生巧
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
代码如下(C++)
nt solve(int m[][11],int w[],int v[],int n)//n代表物品的个数
{
//采用从底到顶的顺序来设置m[i][j]的值
//首先放w[n]
for(int j = 0; j <= c; j++){
if(j < w[n]) m[n][j] = 0; //j小于w[n],放不下,把所对应的值设为0,否则就为可以放置
else m[n][j] = v[n];
}
//对剩下的n-1个物品进行放置。
int i;
for(i = n-1; i >= 1; i--){
for(int j = 0; j <= c; j++)
if(j < w[i]) {
m[i][j] = m[i+1][j];//如果j < w[i]则,表示放不下,它等于上一个位置的值。
}else {
//否则,就考虑是否要放置,原理和递归做法相似
m[i][j] = max(m[i+1][j], m[i+1][j-w[i]] + v[i]);
}
return m[1][c];//m[1][c]就是所求最大值
}
问题描述:
小明是一个喜欢看动画片的人,自从成为ACMer(ACM爱好者)之后,他又迷上了网上做题。做题让他快乐,不过这也是需要付出精力的!! 假设有n道题,Lian做出第i道题后,他可以获得的快乐指数将增加gethappy[i],而消耗掉的精力将是losspow[i]。 假设Lian初始的快乐指数为1,精力为2000。可以理解,如果他消耗完了所有的精力那他得到再多的快乐都没有用。 你的任务就是帮他计算他所能得到的最多的快乐指数,且最后他依然有多余的精力(即至少为1)。
输入格式
第一行输入一个整数n,表示有n个人。(n<=50)
第二行输入n个整数,表示gethappy[1]到gethappy[n]
第三行输入n个整数,表示losspow[1]到losspow[n]。
输出格式
一个整数,表示小明所能获得的最大快乐指数。
输入样例
3
15 23 61
350 1301 1513
输出样例
77