P1123 小偷的背包 - 题解

登录注册上岸

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

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

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

2026年3月22日 16:57

小偷的背包题解：

P1123

回复 0 | 赞 1 | 浏览 165

#include<bits/stdc++.h> using namespace std; int main() { int s; int n; scanf("%d",&s); scanf("%d",&n); int w[n]; int dp[s+3]; ...

2026年3月8日 19:53

小偷的背包题解：

P1123

回复 0 | 赞 5 | 浏览 194

#include <bits/stdc++.h> using namespace std; int main() { int s; cin>>s; int n; cin>>n; int w[n+1]; for (int i = 1;i <= n;i++) { cin>>w[i]; } int dp[n+1][s+1]; for (int i = 0;i <=n;i++) { for (int j ...

2026年2月25日 14:57

从记忆化搜索到1：1翻译成递推【小偷的背包】

P1123

回复 0 | 赞 6 | 浏览 278

一、记忆化搜索由于每个物品选的次数至多选一次，所以本题是一道标准的01背包问题。定义 dfs(i,j) 表示从下标从[0, i]中前 (i + 1) 个物品中选一些，满足重量和恰好等于 j 的成功性。考虑第 i 个物品 i 选或不选： ·不选：问题变成从前 i 个物品中选一些物品，满足重量和恰好等于 j 的成功性，即 dfs(i,j)=dfs(i−1,j)。 ·选：问题变成从前 i 个完全平方数中选一些数（可以重复选），满足元素和恰好等于 j&m...

2026年2月19日 09:45

小偷的背包题解：

P1123

回复 0 | 赞 4 | 浏览 228

#include<bits/stdc++.h> using namespace std; int main() { int dp[1005][1005] = {0};//只有 0 和 1 0 表示不可以 1 表示可以 int w[1005]; int s,n; while(cin >> s >> n){ for(int i=1;i<=n;i++){ cin >> w[i]; } memset(dp,0,sizeof(dp)); dp[0][0] = 1;//前 0 件物品中能拼...

2025年3月16日 14:37

P1123

回复 0 | 赞 18 | 浏览 1.4k

#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 | 赞 2 | 浏览 1.2k

//问题的本质就是是否存在一组非零向量使得其与权重矩阵的点击为背包容量 #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 | 赞 27 | 浏览 1.5k

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

折翼的小鸟先生

2024年9月8日 13:29

小偷的背包题解：

P1123

回复 0 | 赞 5 | 浏览 1.7k

简单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 | 赞 9 | 浏览 1.5k

把重量看成体积 #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 | 赞 1 | 浏览 1.3k

#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 ==...

1
2

题目小偷的背包

题解数量17

发布题解在线答疑

热门题解

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

2 01背包问题

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

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

5 从记忆化搜索到1：1翻译成递推【小偷的背包】

6 小偷的背包题解：

7 小偷的背包题解：

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

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

10 小偷的背包题解：