主站
DreamJudge
院校信息
专业题库
模拟考试
机试真题
专业课程
答疑区
兑换中心
登录
注册
上岸
以下题解仅供学习参考使用。
抄袭、复制题解,以达到刷AC率/AC数量或其他目的的行为,在N诺是严格禁止的。
N诺非常重视学术诚信。此类行为将会导致您成为作弊者。具体细则请查看N诺社区规则。
我与代码的故事
2024年5月19日 00:17
简单背包问题(一维01背包, 题目中体积和价值是一样的) 题解:
P1035
回复 0
|
赞 1
|
浏览 366
注意是多组测试输入 (没注意就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
|
赞 0
|
浏览 524
代码: #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...
xjnotywlq
2024年3月22日 16:06
简单背包问题 题解:dp
P1035
回复 0
|
赞 0
|
浏览 584
#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...
Hegel
2023年3月28日 14:44
简单背包问题,采用贪心枚举法,欢迎指正
P1035
回复 1
|
赞 1
|
浏览 2.1k
#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
|
浏览 662
#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
|
赞 0
|
浏览 733
#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
|
赞 0
|
浏览 898
#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
|
赞 1
|
浏览 6.0k
思路 使用动态规划的思想,用 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...
James
2021年2月20日 13:06
二进制状态枚举法
P1035
回复 0
|
赞 0
|
浏览 7.7k
#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
|
赞 5
|
浏览 9.8k
#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开始判断:...
1
2
题目
简单背包问题
题解数量
13
发布题解
热门题解
1
背包问题:简单递归思想(也可写成动态规划)
2
题解:简单背包问题
3
简单背包问题,采用贪心枚举法,欢迎指正
4
动态规划入门 - 简单背包
5
简单背包问题(一维01背包, 题目中体积和价值是一样的) 题解:
6
简单背包问题 题解:dp
7
简单背包问题(c++)
8
DP优化解法同1123小偷的背包,dp数组大一点就过了
9
简单背包问题 题解:贪心算法
10
简单背包问题 题解: