题目要求:简单的背包问题。设有一个背包,可以放入的重量为 s。现有 n 件物品,重量分别为 w 1 ,w 2 …,w n , (1≤i≤n) 均为正整数,从 n 件物品中挑选若干件,使得放入背包的重量之和正好为 s。找到一组解即可。如果有解输出“yes”,如果没有解,则输出“no” 第一行是物品总件数和背包的载重量,第二行为各物品的重量。各所选物品的序号和重量。 输入示例: 5 10 1 2 3 4 5 输出示例: yes
时间: 2024-02-15 15:02:58 浏览: 12
以下是符合题目要求的 C 语言代码:
```c
#include <stdio.h>
#include <stdbool.h>
bool findSubset(int w[], int n, int s) {
bool subset[n+1][s+1];
// 如果 s = 0,那么无论如何都有一个空集合作为解
for (int i = 0; i <= n; i++) {
subset[i][0] = true;
}
// 如果 n = 0,而 s > 0,那么无解
for (int i = 1; i <= s; i++) {
subset[0][i] = false;
}
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= s; j++) {
if (j < w[i-1]) {
subset[i][j] = subset[i-1][j];
}
else {
subset[i][j] = subset[i-1][j] || subset[i-1][j-w[i-1]];
}
}
}
return subset[n][s];
}
int main() {
int n, s;
scanf("%d %d", &n, &s);
int w[n];
for (int i = 0; i < n; i++) {
scanf("%d", &w[i]);
}
if (findSubset(w, n, s)) {
printf("yes");
}
else {
printf("no");
}
return 0;
}
```
这段代码实现了简单的背包问题。它使用了动态规划的思想,使用一个二维布尔型数组 `subset` 来表示是否能够选出一些物品,使得它们的重量之和正好为 `s`。在计算 `subset[i][j]` 时,如果当前物品的重量 `w[i-1]` 大于 `j`,那么就不能选这个物品,此时 `subset[i][j] = subset[i-1][j]`;否则,可以选或不选当前物品,取两者的或运算,即 `subset[i][j] = subset[i-1][j] || subset[i-1][j-w[i-1]]`。最后,如果 `subset[n][s]` 为 `true`,说明存在一组解,输出 "yes",否则输出 "no"。
相关推荐
![](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)
![text/plain](https://img-home.csdnimg.cn/images/20210720083646.png)
![text/x-c](https://img-home.csdnimg.cn/images/20210720083646.png)