P1035 简单背包问题 - 题解

登录注册上岸

以下题解仅供学习参考使用。

抄袭、复制题解，以达到刷AC率/AC数量或其他目的的行为，在N诺是严格禁止的。

N诺非常重视学术诚信。此类行为将会导致您成为作弊者。具体细则请查看N诺社区规则。

机试过过过·

2025年4月5日 17:38

简单背包问题题解：

P1035

回复 1 | 赞 4 | 浏览 222

#include<bits/stdc++.h> // 包含标准库，方便使用各种功能 using namespace std; int main(){ int s, n; // 定义变量s表示背包的容量，n表示物品的数量 while(cin >> s >> n){ // 多组测试数据，循环读取输入 int a[n+1]; // 定义数组a，存储每个物品的重量，大小为n+1（方便从1开始索引） for(int i = 1; i <= n; i++) cin >> a[i]...

2025年1月25日 12:33

疑问：请问内层循环为什么要从大到小啊？

P1035

回复 4 | 赞 24 | 浏览 675

一维数组要从大到小遍历我能理解，二维数组的第二个for循环为什么也要从大到小才行呢？ //1035-简单背包问题 #include<bits/stdc++.h> using namespace std; int main(){ int s,n; while(cin>>s>>n){ int w[n+1]; int dp[n+1][s+1]; for(int i=1;i<=n;i++){ cin>>w[i]; } memset(dp,0,sizeof(d...

2024年5月19日 00:17

简单背包问题(一维01背包，题目中体积和价值是一样的) 题解：

P1035

回复 0 | 赞 38 | 浏览 998

注意是多组测试输入（没注意就WA一次） #include<bits/stdc++.h> using namespace std; const int N = 1010; int dp[N], w[N]; int n, m; int main() { while(cin >> m >> n) { memset(dp, 0, sizeof dp); for(int i = 1; i <= n; i ++) cin >> w[i]; for(int i = 1; i ...

2024年4月21日 20:29

简单背包问题题解：

P1035

回复 0 | 赞 9 | 浏览 926

代码： #include <iostream> #include <vector> using namespace std; bool canAchieveSum(const vector<int>& weights, int s) { // 创建动态规划数组，大小为s+1 vector<bool> dp(s + 1, false); dp[0] = true; // 初始化，0重量总是可达的 // 遍历每个物品 for (int weight : weigh...

2024年3月22日 16:06

简单背包问题题解：dp

P1035

回复 0 | 赞 17 | 浏览 994

#include <stdio.h> #include <stdlib.h> int s,n; int w[1000]; int dp[1000][1000]; int max(int a,int b) { if(a>=b)return a; else return b; } int main() { while(scanf("%d%d",&s,&n)!=EOF) { //dp[i][j]放前i个物品，能不能刚好装下容量为j的物品 for...

2023年3月28日 14:44

简单背包问题，采用贪心枚举法，欢迎指正

P1035

回复 1 | 赞 6 | 浏览 2.4k

#include <iostream> using namespace std; int main() { int sum, n; while (cin >> sum >> n) { int* a = new int[n]; for (int i = 0; i < n; i++) cin >> a[i]; for (int i = 0; i < n&&sum>0;) { if (sum - a[i] >= 0) sum -= a[i]; ...

DestinyCares+++

2024年3月14日 15:16

简单背包问题题解：

P1035

回复 0 | 赞 0 | 浏览 916

#include<iostream> #include<cstring> #include<map> #include<string> using namespace std; const int maxn = 200; int dp[maxn][maxn] = { 0 };//前i个物品是否能凑成重量为j； int w[maxn]; int main() { int s, n; while (cin>>s>>n) { ...

2024年2月5日 18:09

简单背包问题题解：贪心算法

P1035

回复 0 | 赞 1 | 浏览 1.0k

#include <iostream> using namespace std; int main(){ int weigh=0,n=0,index=0; int a[10000]; while(cin >>weigh){ cin >>n; for(int i=0;i<n;i++) cin >> a[i]; //冒泡排序降序================================== for(int i=0;i<n;i++) for(int j=n-2;...

2023年8月5日 13:51

DP优化解法同1123小偷的背包，dp数组大一点就过了

P1035

回复 3 | 赞 3 | 浏览 1.2k

#include<cstdio> #include<cstring> int main() { int S, n; while(scanf("%d%d", &S, &n) != EOF){ int dp[201], w[101]; memset(dp, 0, sizeof(dp)); dp[0] = 1; for (int i = 1; i <= n; i++) scanf("%d", &w[i]); for (int i = 1; i <= n; i++) for (int j ...

帅就一个字

2022年7月3日 17:36

动态规划入门 - 简单背包

P1035

回复 0 | 赞 19 | 浏览 6.7k

思路使用动态规划的思想，用 weight[1...n] 表示各个物件的重量，多个物件被选择后，最后加上物件 weight[m] 刚好满足总重量为 s ，那么必须满足 s - weight[m] 与前面选择的物件重量之和相等，重复这样操作的时候，s变成了 s - weight[m]，物件数量在原有的基础上减少1个，某个被选择的物件是重量weight[n]。从而我们可以利用递归判断是否满足条件： if(packet(s - weight[n - 1], n - 1)){ return true; } else return packet(s,n...

1
2

题目简单背包问题

题解数量15

发布题解在线答疑

热门题解

1 简单背包问题(一维01背包，题目中体积和价值是一样的) 题解：

2 疑问：请问内层循环为什么要从大到小啊？

3 动态规划入门 - 简单背包

4 简单背包问题题解：dp

5 背包问题：简单递归思想（也可写成动态规划）

6 简单背包问题题解：

7 简单背包问题，采用贪心枚举法，欢迎指正

8 题解：简单背包问题

9 简单背包问题题解：

10 DP优化解法同1123小偷的背包，dp数组大一点就过了