又快到了寒假时间,说到寒假,免不了出去玩耍,小蒋今天要去郊游,她想带点零食去,但是她的包包大小有限,所以她需要在 n 个零食中挑选若干零食装入包包,最多能装多满?假设包包的大小为 m ,每袋零食的大小为 A[i]。C语言完整代码
时间: 2024-06-13 10:08:47 浏览: 14
```c
#include <stdio.h>
int max(int a, int b) {
return a > b ? a : b;
}
int main() {
int n, m;
scanf("%d %d", &n, &m);
int A[n+1];
for (int i = 1; i <= n; i++) {
scanf("%d", &A[i]);
}
int dp[n+1][m+1];
for (int i = 0; i <= n; i++) {
for (int j = 0; j <= m; j++) {
dp[i][j] = 0;
}
}
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
if (j >= A[i]) {
dp[i][j] = max(dp[i-1][j], dp[i-1][j-A[i]]+A[i]);
} else {
dp[i][j] = dp[i-1][j];
}
}
}
printf("%d\n", dp[n][m]);
return 0;
}
```
相关问题
又快到了寒假时间,说到寒假,免不了出去玩耍,小蒋今天要去郊游,她想带点零食去,但是她的包包大小有限,所以她需要在n个零食中挑选若干零食装入包包,最多能装多满?假设包包的大小为m,每袋零食的大小为A[i]。 样例
可以使用动态规划算法来解决这个问题。具体来说,可以定义一个二维数组dp,其中dp[i][j]表示在前i个零食中选择一些能否恰好装满容量为j的背包。对于每个零食i,可以选择不装入背包,此时dp[i][j]的值与dp[i-1][j]相同;或者选择装入背包,此时dp[i][j]的值为dp[i-1][j-A[i]]加上当前零食的大小A[i]。最终,dp[n][m]的值即为能够恰好装满背包的最大零食大小。
以下是一个Python实现的例子:
```python
def max_snacks(n, m, A):
dp = [[0] * (m + 1) for _ in range(n + 1)]
for i in range(1, n + 1):
for j in range(1, m + 1):
if j >= A[i-1]:
dp[i][j] = max(dp[i-1][j], dp[i-1][j-A[i-1]] + A[i-1])
else:
dp[i][j] = dp[i-1][j]
return dp[n][m]
```
其中,n表示零食的数量,m表示背包的容量,A是一个长度为n的列表,表示每个零食的大小。
例如,如果有4个零食大小是[2, 3, 5, 7],包包的大小为11,可以选择[2, 3, 5]装入背包,最多可以装满10的空间。如果包包的大小为12,可以选择[2, 3, 7]装入背包,最多可以装满12的空间。
--相关问题--:
1. 动态规划算法的时间复杂度是多少?
2. 如果每个零食有一个对
将typora笔记复制到csdn
你可以按照以下步骤将 Typora 笔记复制到 CSDN:
1. 打开 Typora 并进入你想要复制的笔记。
2. 选择整个笔记内容:你可以使用快捷键 Ctrl + A (Windows) 或 Command + A (Mac),或者鼠标左键点击并拖动选择全部内容。
3. 复制笔记内容:使用快捷键 Ctrl + C (Windows) 或 Command + C (Mac),或者右键点击选择 "复制"。
4. 打开 CSDN 并进入你想要粘贴笔记的位置。
5. 点击编辑按钮,进入编辑模式。
6. 粘贴笔记内容:使用快捷键 Ctrl + V (Windows) 或 Command + V (Mac),或者右键点击选择 "粘贴"。
7. 根据需要进行格式调整:在 CSDN 编辑器中,你可能需要调整一些格式,如标题、列表、代码块等。
请注意,CSDN的编辑器可能与 Typora 的样式和功能有所不同,因此一些特定的格式可能需要手动调整。确保在复制和粘贴过程中保留原始笔记的格式,并仔细检查粘贴后的内容以确保一致性和正确性。
相关推荐
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)
![rar](https://img-home.csdnimg.cn/images/20210720083606.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)