P1035 简单背包问题 - 题解

登录注册上岸

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

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

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

2024年2月5日 18:09

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

P1035

回复 0 | 赞 1 | 浏览 1.6k

#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 | 赞 4 | 浏览 1.9k

#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 | 赞 20 | 浏览 7.3k

思路使用动态规划的思想，用 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...

2021年2月20日 13:06

二进制状态枚举法

P1035

回复 0 | 赞 0 | 浏览 8.8k

#include <iostream> #include <algorithm> #include <math.h> using namespace std; const int maxn=1e5; int s[maxn]; int v,n; int main(){ while(scanf("%d %d",&v,&n)!=EOF){ for(int i=0;i<n;i++)...

2021年1月10日 23:16

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

P1035

回复 0 | 赞 12 | 浏览 10.7k

#include using namespace std; /*设有一个背包可以放入的物品重量为S，现有n件物品，重量分别是w1，w2，w3，…wn。问能否从这n件物品中选择若干件放入背包中，使得放入的重量之和正好为S。如果有满足条件的选择，则此背包有解，否则此背包问题无解。算法思想是划分子问题，对于背包数组里的每个元素，有两种可能： 1.当前元素在最后成功的组里，即剩余的元素中有组合为（s-当前元素的值）的情况； 2.当前元素不在，则继续判断剩余元素；举个例子：s=20,w[5]={1,3,5,7,9} 从9开始判断：...

2020年3月25日 10:34

简单背包问题（c++）

P1035

回复 0 | 赞 1 | 浏览 15.9k

注意：有多组测试用例 #include<iostream> #include<cstring> using namespace std; int main() { int s, n; while (cin >> s >> n) { int* w = new int[n]; for (int i = 0; i < n; i++) cin >> w[i]; bool* dp = new bool[s+1]; memset(dp, 0, sizeof(dp)); d...

2020年3月14日 19:07

直接套用01背包的公式就好了

P1035

回复 0 | 赞 1 | 浏览 11.9k

#include<bits/stdc++.h> using namespace std; int const maxn = 10000; int dp[maxn]; int w[maxn]; int main(){ int s,n; while(cin>>s>>n){ fill(dp,dp+maxn,10000); dp[0]=0; for(int i=0;i<n;i++){ cin>>w[i]; }...

2020年3月15日 21:32

题解：简单背包问题

P1035

回复 0 | 赞 5 | 浏览 12.0k

很经典的01背包模型 #include <bits/stdc++.h> using namespace std; int w[1000], dp[1000], s, n; int main() { while (cin >> s >> n) { memset(dp, 0, sizeof(dp)); memset(w, 0, sizeof(w)); for (int i = 1; i <= n; i++) cin >> w[i]; //开始动规，一定要从后往前更新 ...

1
2

题目简单背包问题

题解数量18

发布题解在线答疑

热门题解

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

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

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

4 简单背包问题题解：dp

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

6 简单背包问题题解：

7 简单背包问题题解：

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

9 题解：简单背包问题

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