P1123 小偷的背包 - 题解

登录注册上岸

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

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

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

2025年3月16日 14:37

P1123

回复 0 | 赞 2 | 浏览 479

#include <bits/stdc++.h> using namespace std; int main() { int s,n; cin>>s>>n; vector<int> wi(n); for(int i=0;i<n;i++){ cin>>wi[i]; } vector<bool> dp(s+1,false); dp[0]=true;//0默认可以 for(int i=0;i<n;i++){ for(in...

2025年3月16日 13:29

小偷的背包题解：

P1123

回复 0 | 赞 1 | 浏览 430

//问题的本质就是是否存在一组非零向量使得其与权重矩阵的点击为背包容量 #include<bits/stdc++.h> using namespace std; int main(){ int s,n; while(cin>>s>>n){ int a[n+1];//0代表不装，1代表装，最后如果全零代表无解 for(int i=0;i<n;i++){ a[i]=0;//初始化0 } int w[n+1];//代表权重 for(int i=0;i<n;i++){ cin>&...

2025年1月31日 09:45

小偷的背包题解：详细解释一下适配背包问题

P1123

回复 0 | 赞 19 | 浏览 781

适配背包问题有两种，第一种就是这种，不存在最优结果的适配问题，也就是我们只考虑能否放下的可能性是否存在，但是不考虑价值，第二种就是考虑价值的。对于第一种的解法，其实很简单，我们只需要利用布尔型的背包解决即可，全部的情况就只有这几种，当前物品对于当前背包大小，能放入，则判定，这时候不需要判定是否放入，因为不放入必然是不可能适配的，放入，则判定是否收缩前是适配的状态，假如大小不足，无法放入，则直接取上一个物品该大小的情况即可，最后的方程如下 dp[i][j] = dp[i−1][j−w[i−1] （ if j&...

折翼的小鸟先生

2024年9月8日 13:29

小偷的背包题解：

P1123

回复 0 | 赞 5 | 浏览 1.1k

简单dp,直接转移就行，题目没给范围但1000就够了 #include<cstdio> #include<iostream> #include<cstring> #include<queue> #include<stack> #include<algorithm> using namespace std; #define maxn 10000+10 #define inf 0x3f3f3f3f #define ll long long int s,n; int a[maxn]; in...

2024年7月14日 19:03

小偷的背包(01背包) 题解：

P1123

回复 0 | 赞 6 | 浏览 929

把重量看成体积 #include<bits/stdc++.h> using namespace std; const int N = 1010; int dp[N], v[N]; int n, s; int main() { cin >> s >> n; for(int i = 1; i <= n; i ++) scanf("%d", &v[i]); for(int i = 1; i <= n; i ++) for(int j = s; j >= ...

2024年3月24日 16:42

小偷的背包题解：组合数问题，回溯法直接套模板就行

P1123

回复 0 | 赞 0 | 浏览 902

#include<iostream> #include<vector> #include<string> #include<algorithm> using namespace std; int weight[10000]; int S; int n; bool flag = false; void traceback(int w, int i) { //cout << w << endl; if (w ==...

2024年3月17日 17:33

小偷的背包题解：题目和简单背包问题一样的为什么这边错误50%

P1123

回复 2 | 赞 2 | 浏览 872

#include<bits/stdc++.h> using namespace std; bool cmp(int a,int b){ return a>b; } int main(){ int weight=0,n,temp; while(cin>>weight>>n){ int a[n]; for(int i=0;i<n;i++){ cin>>a[i]; } sort(a,a+n,cmp); for(int i=0;i<n&&weight&g...

2023年8月5日 13:36

DP空间优化O(n)，或算法（内存140kb）

P1123

回复 0 | 赞 2 | 浏览 924

#include<stdio.h> int dp[31], w[21]; int main() { int S, n; scanf("%d%d", &S, &n); for (int i = 1; i <= n; i++) scanf("%d", &w[i]); dp[0] = 1; for (int i = 1; i <= n; i++) for (int j = S; j >= w[i]; j--) dp[j] |= dp[j - w[i]]; if (dp[S]) puts("y...

2023年3月31日 20:57

小偷的背包：dfs实现动态规划

P1123

回复 0 | 赞 4 | 浏览 2.2k

knap( s, n) = ︳true, s= 0 ︳false, s< 0 ︳false, s> 0 且n<0 ︳knap( s, n- 1) 或knap(s- Wn, n- 1) , s> 0 且n>= 1; 代码如下： # include<stdio.h> # include<string.h> int date[1005]; int f(int w, int s) { if(w == 0) return 1;//正好 if(w<0 || w>0 &&...

2022年8月15日 16:11

1123 01背包问题+复习完全背包（简述重点区别）

P1123

回复 0 | 赞 7 | 浏览 5.7k

若仅仅只看题解跳转part2 part1背包问题 01背包 01背包问题在网上也有很多解了。这里只说一些比较重要的，能够快速回忆关键点 n为物品数，s为总容量 dp[i][j]表示在遍历到第i个物品时，剩余容量为j时的背包的最大价值（很多人描述i为把前i个物品装入时的最大价值，但是index为i时，前i个物品并非全部装入了背包，而是有选择性的。这很容易误导新手）因为我们使用j来表示背包的容量，所以j（而不是j-1）就表示容量为j，所以背包问题中所有的数组都建议从1开始，让0表示真正的“空”，而不...

1
2

题目小偷的背包

题解数量13

发布题解在线答疑

热门题解

1 小偷的背包题解：详细解释一下适配背包问题

2 1123 01背包问题+复习完全背包（简述重点区别）

3 小偷的背包(01背包) 题解：

4 小偷的背包题解：

5 小偷的背包：dfs实现动态规划

6 01背包问题

7 DP空间优化O(n)，或算法（内存140kb）

8 小偷的背包题解：题目和简单背包问题一样的为什么这边错误50%

9 1123-小偷的背包（c语言）

10 小偷的背包题解：