P1123 小偷的背包 - 题解

登录注册上岸

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

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

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

折翼的小鸟先生

2024年9月8日 13:29

小偷的背包题解：

P1123

回复 0 | 赞 0 | 浏览 293

简单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 | 赞 1 | 浏览 329

把重量看成体积 #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 | 浏览 508

#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 | 赞 0 | 浏览 440

#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 | 赞 1 | 浏览 621

#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 | 赞 1 | 浏览 1.8k

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 | 赞 1 | 浏览 5.1k

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

2022年3月17日 14:36

C++

P1123

回复 0 | 赞 0 | 浏览 4.6k

#include<iostream> #include<vector> using namespace std; int main(){ int S; int n; cin >> S; cin >> n; vector<int> a; for(int i = 0; i < n; i...

2021年3月18日 10:23

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

P1123

回复 0 | 赞 0 | 浏览 9.6k

分析这是一个简单背包问题。推荐学习视频：https://www.bilibili.com/video/BV1AJ411Y7Fm?p=29 代码 #include <stdio.h> #include <string.h> int main() { int dp[100][100] = {0};//定义背包数组。值只为0或1；0表示不可以，1表示可以 int w[100];//定义重量数组 int s, n; while(scanf("%d%d", &s, &n)!=EOF) ...

2021年2月20日 13:34

二进制状态枚举

P1123

回复 0 | 赞 0 | 浏览 7.6k

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

题目小偷的背包

题解数量10

热门题解

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

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

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

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

5 小偷的背包题解：

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

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

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

9 C++

10 二进制状态枚举