动态规划---01背包问题（1）

模型框架：有一个空间为V的容器，需要从n个物品（包含属性：所占空间volume，价值value）中挑选几件物品使得容器中的价值最大。

问题解决思路：

比如有一个口袋，容量是4，有3个物品，分别是编号1：吉他（空间占用：1；价值：1500）、编号2：音响（空间占用：4；价值：3000）、编号3：笔记本电脑（空间占用：3；价值：2000），问如何挑选使得口袋能得到最大价值。

有人会说，那我一个一个尝试过去就能知道了，只是时间花的久一点（这里时间久的可不是一点点←_←）

举个例子来说：我现在这个例子有3个物品，排列组合一下就有（空）（1）（2）（3）（1,2）（1,3）（2,3）（1,2,3）8种情况，要是4个就有2⁴=16，5个就有2⁵=32种，这种算法运行时间为O(2ⁿ），简直不要太慢了好嘛(ﾟｰﾟ)

所以这就要提到今天需要新学的算法动态规划中的01背包问题

动态规划一般是把大问题拆分为小问题，用表格的方式来解决问题

假设现在我们只有编号1的吉他可以选，

物品容量	1	2	3	4
吉他（1/1500）	1500（吉他）	1500（吉他）	1500（吉他）	1500（吉他）

现在我们再加上编号2的音响

物品容量	1	2	3	4
吉他（1/1500）	1500（吉他）	1500（吉他）	1500（吉他）	1500（吉他）
音响（4/3000）	1500（吉他）	1500（吉他）	1500（吉他）	3000（音响）

我们再加上编号3的笔记本电脑

物品容量	1	2	3	4
吉他（1/1500）	1500（吉他）	1500（吉他）	1500（吉他）	1500（吉他）
音响（4/3000）	1500（吉他）	1500（吉他）	1500（吉他）	3000（音响）
笔记本电脑（3/2000）	1500（吉他）	1500（吉他）	2000（笔记本电脑）	3500（笔记本电脑+吉他）

通过这个过程，可以观察到其中包含了一个公式

dp[i][j]=max(dp[i-1][j],dp[i-1][j-当前物品占用空间]+当前物品的价值)
前半部分指的是当前这个物品的容量要大于我现在有的容量（也就是装不下这个物品了，这个时候我们需要用没有这个物品的情况下，能获取的最大价值），或者是放弃（不考虑）当前这个物品
后半部分说的是：能装下当前这个物品，但是还有多余的空间，那就去对应的那个空间看看，这个剩余的空间能装下最多是多少的价值
最后取其中最大的，也就是我们需要求的答案了

既然算法了解了，来几道题测一测(ﾟｰﾟ)

例题1：

原题链接

Bone Collector

Problem Description

Many years ago , in Teddy’s hometown there was a man who was called “Bone Collector”. This man like to collect varies of bones , such as dog’s , cow’s , also he went to the grave …
The bone collector had a big bag with a volume of V ,and along his trip of collecting there are a lot of bones , obviously , different bone has different value and different volume, now given the each bone’s value along his trip , can you calculate out the maximum of the total value the bone collector can get ?

Input

The first line contain a integer T , the number of cases.
Followed by T cases , each case three lines , the first line contain two integer N , V, (N <= 1000 , V <= 1000 )representing the number of bones and the volume of his bag. And the second line contain N integers representing the value of each bone. The third line contain N integers representing the volume of each bone.

Output

One integer per line representing the maximum of the total value (this number will be less than 2³¹).

Sample Input

1 5 10 1 2 3 4 5 5 4 3 2 1

Sample Output

问题描述：那个人有一个袋子，袋子容量为V，需要收集的骨头分别有容量weight和价值value，给你一些骨头的容量和价值，需要你求出这个袋子可以装下骨头的最大价值。

方法一：

 1 //二维数组
 2 #include <stdio.h>
 3 #include <string.h>
 4 
 5 int T,n,v;
 6 int value[1005];//价值
 7 int volume[1005];//容量
 8 int s[1005][1005];//存最大价值的数组
 9 int maxx(int a,int b);
10 int main(void)
11 {
12     int i,j,k;
13     scanf("%d",&T);
14     while(T--)
15     {
16         memset(value,0,sizeof(value));
17         memset(volume,0,sizeof(volume));
18         memset(s,0,sizeof(s));//这个必须要清空
19         scanf("%d%d",&n,&v);
20         for(i=1;i<=n;i++)
21             scanf("%d",&value[i]);
22         for(i=1;i<=n;i++)
23             scanf("%d",&volume[i]);
24         for(i=1;i<=n;i++)
25         {
26             for(j=0;j<=v;j++)
27             {
28                 if(volume[i]<=j)//装的下
29                 {
30                     s[i][j]=maxx(s[i-1][j],value[i]+s[i-1][j-volume[i]]);
31                     //比较没有装当前这个物品的价值 和 装了当前这个物品的价值+剩余空间的最大价值
32                 }
33                 else//装不下
34                 {
35                     s[i][j]=s[i-1][j];
36                 }
37             }
38         }
39         printf("%d
",s[n][v]);//最后一个位置就是最大价值
40 
41     }
42     return 0;
43 }
44 
45 int maxx(int a,int b)
46 {
47     return a>b?a:b;
48 }

方法二：

 1 #include <stdio.h>
 2 #include <string.h>
 3 
 4 int maxx(int a,int b);
 5 
 6 int dp[1005];//存放最大价值的数组
 7 int value[1005];//价值
 8 int volume[1005];//容量
 9 
10 int main(void)
11 {
12     int T,n,v;
13     int i,j,k;
14     scanf("%d",&T);
15     while(T--)
16     {
17         memset(dp,0,sizeof(dp));//必需清空
18         scanf("%d%d",&n,&v);
19         
20         for(i=1;i<=n;i++)
21             scanf("%d",&value[i]);
22         for(i=1;i<=n;i++)
23             scanf("%d",&volume[i]);
24         
25         for(i=1;i<=n;i++)
26         {
27             for(j=v;j>=volume[i];j--)//注意这个要从后往前倒序，如果不这样就会不止取到一个当前这个物品
　　　　　　　　　　　　　　　　　　　　　　　　（比如：物品容量是1，从前往后排，容量为2的时候取到了自己再去取容量为1的自己，
　　　　　　　　　　　　　　　　　　　　　　　　但是物品只有一个，所以为了避免这个问题，就从后往前取了）
28             {
29                 dp[j]=maxx(dp[j],dp[j-volume[i]]+value[i]);
30             }
31         }
32         printf("%d
",dp[v]);
33     }
34 
35     return 0;
36 }
37 
38 int maxx(int a,int b)
39 {
40     return a>b?a:b;
41 }