雪花飘飘

用户名：zhuo100204

访问量：1791

签　名：

傲气不可有，傲骨不可无。

等　　级
排　　名	3739
经　　验	1854
参赛次数	2
文章发表	10
年　　龄	12
在职情况	学生
学　　校
专　　业

　　自我简介：

嬉皮笑脸也好，脚踏实地也好，只要做好自己，都是好的。

TA的其他文章

数的统计——python实现
浏览：105

数字逆序输出——两行代码
浏览：101

耍个小聪明
浏览：256

你可能喜欢

C语言程序设计教程（第三版）课后习题6.11 （C语言代码）

01背包问题——递归的方法

　　作者: 雪花飘飘　　　　发表时间：2022-05-28 11:13:01 浏览：632　|　评论：0　

原题链接：信息学奥赛一本通T1267-01背包问题

#01背包问题
在信息学奥赛一本通中， 01背包问题采用的是循环的方法。但是循环有一个明显的问题，就是太麻烦，也不好理解。
这里我们采用递归的方法来解决这个问题。
首先我们定义一个函数work()，这个函数是我们的算法的核心。
接下来是2个数组，分别是W和C。他们分别存储体积和价值。
对于动态规划而言，事实上就是一个简单的递归，虽然没有明说，但是事实上他就是完成了一个递归的操作。
首先我们注意到， Work需要有2个参数i和v，i表示第i件物品，v表示这个背包剩余的容量。
假如i等于0，那么就说明根本没有物品，所以我们可以直接返回0。
```cpp
int work(int v,int i){
    if(i==0) return 0;
```
很好，接下来考虑第2种情况，假如i等于1，那么就只有两种情况：
1.参数V比第一件物品的体积要小。在这种情况下，就可以直接返回0，也就是说无法放入任何物品。
2.参数V比第一件物品的体积要大。在这种情况下，就可以直接返回c[0]。
```cpp
    if(i==1) return (v<w[0])?0:c[0];
```
接下来考虑第3种情况。如果i>1，那么有2种情况：
1.参数V比第i件物品的体积要小。在这种情况下，就可以直接返回work(v,i-1)，也就是说无法放入第i件物品。
2.参数V比第i件物品的体积要大。在这种情况下，我们要进行第二步决策。也就是说，比较`work(v,i-1)`和`work(v-w[i-1],i-1)+c[i-1]`的大小，也就是放与不放的大小。
```cpp
    if((v<w[i-1])) return work(v,i-1);
    int c1=work(v,i-1);
    int c2=work(v-w[i-1],i-1)+c[i-1];
```
最后执行返回的操作：
```cpp
    return (c1>c2)?c1:c2;
```
接下来在主函数中调用这个函数即可。
```cpp
int main()
{
    int m,n,v;
    cin  >> m >> n;
    for(int i=0;i<n;i++) {cin >> w[i] >> c[i];}
    v=work(m,n);
    cout << v << endl;
    return 0;
}
```
最后，完整代码：
```cpp
#include<iostream>
using namespace std;
int w[31],c[31];
int work(int v,int i){
    if(i==0) return 0;
    if(i==1) return (v<w[0])?0:c[0];
    if((v<w[i-1])) return work(v,i-1);
    int c1=work(v,i-1);
    int c2=work(v-w[i-1],i-1)+c[i-1];
    return (c1>c2)?c1:c2;
}
int main()
{
    int m,n,v;
    cin  >> m >> n;
    for(int i=0;i<n;i++) {cin >> w[i] >> c[i];}
    v=work(m,n);
    cout << v << endl;
    return 0;
}
```

0.0分

2 人评分

看不懂代码解释一下代码? 或者生成一段代码？试试AI编程助手吧

雪花飘飘

TA的其他文章

你可能喜欢

用筛法求之N内的素数。（C语言代码）

C语言程序设计教程（第三版）课后习题6.11 （C语言代码）

C语言程序设计教程（第三版）课后习题6.9 （C语言代码）

C语言程序设计教程（第三版）课后习题8.9 （C语言代码）

哥德巴赫曾猜测（C语言代码）

01背包问题——递归的方法

评论区

精彩推荐

数组输出（C语言代码）错误？？？

WU-C语言程序设计教程（第三版）课后习题12.1 （C++代码）

有关字符，字符串的输入输出函数说明

演讲大赛评分（C语言代码）

Tom数（C语言代码）

【魔板】（C++代码）

C语言程序设计教程（第三版）课后习题7.4 （C语言代码）

1415题求解

C二级辅导-阶乘数列（C语言代码）

C语言程序设计教程（第三版）课后习题10.7 指针（C语言代码）

雪花飘飘

TA的其他文章

你可能喜欢

用筛法求之N内的素数。 （C语言代码）

C语言程序设计教程（第三版）课后习题6.11 （C语言代码）

C语言程序设计教程（第三版）课后习题6.9 （C语言代码）

C语言程序设计教程（第三版）课后习题8.9 （C语言代码）

哥德巴赫曾猜测 （C语言代码）

01背包问题——递归的方法

评论区

精彩推荐

数组输出 （C语言代码）错误？？？

WU-C语言程序设计教程（第三版）课后习题12.1 （C++代码）

有关字符，字符串的输入输出函数说明

演讲大赛评分 （C语言代码）

Tom数 （C语言代码）

【魔板】 （C++代码）

C语言程序设计教程（第三版）课后习题7.4 （C语言代码）

1415题求解

C二级辅导-阶乘数列 （C语言代码）

C语言程序设计教程（第三版）课后习题10.7 指针（C语言代码）

用筛法求之N内的素数。（C语言代码）

哥德巴赫曾猜测（C语言代码）

　　评论区

数组输出（C语言代码）错误？？？

演讲大赛评分（C语言代码）

Tom数（C语言代码）

【魔板】（C++代码）

C二级辅导-阶乘数列（C语言代码）