01背包问题

痛定思痛。 2022-05-26 12:18 236阅读 0赞

简单背包问题

设有一个背包可以放入的物品重量为S，现有n件物品，重量分别是w1，w2，w3，…wn。

问能否从这n件物品中选择若干件放入背包中，使得放入的重量之和正好为S。

如果有满足条件的选择，则此背包有解，否则此背包问题无解。

#### 输入 ####

输入数据有多行，包括放入的物品重量为s，物品的件数n，以及每件物品的重量（输入数据均为正整数）

多组测试数据。

#### 输出 ####

对于每个测试实例，若满足条件则输出“YES”，若不满足则输出“NO“

#### 样例输入 ####

20 5
    1 3 5 7 9

#### 样例输出 ####

YES

#include<iostream>
    #include<stdio.h>
    using namespace std;
    
    int gvalue[1000];
    
    int packet(int weight, int num) {
    	if(weight == 0){
    		return 1;
    	}
    	// 如果重量小于0 或 没有东西可选了就无解
    	if(weight < 0 || weight > 0 && num < 0) {
    		return 0;
    	}
    	//如果前num - 1个数中有解那就有解， 用上第num个数
    	if( packet(weight - gvalue[num - 1], num - 1)) {
    		return 1;
    	} else {
    		//如果前num - 1个数中无解， 就跳过第num个数
    		return  packet(weight , num - 1);
    	}
    }
    
    
    int main()
    {
    	int weight, num;
    	while(EOF != scanf("%d%d", &weight, &num)){
    		for(int i = 0; i < num ; i++) {
    			cin >> gvalue[i];
    		}
    		if(packet(weight, num)){
    			printf("YES\n");
    		} else {
    			printf("NO\n");
    		}
    	}
    	return 0;
    }

发表评论取消回复

表情：

评论列表（有 0 条评论，236人围观）

还没有评论，来说两句吧...

相关阅读

相关 01背包问题

[0-1背包问题][0-1] Reference: https://www.jianshu.com/p/a66d5ce49df5 问题描述： 0-1背包问题：给定

﹏ヽ暗。殇╰゛Y/ 2022年10月11日 13:40/ 0 赞/ 256 阅读

相关 01背包问题

1.题目有N件物品和一个容量为V的背包。第i件物品的成本是c\[i\]，价值是w\[i\]。求解将哪些物品装入背包可使价值总和最大，要求是：物品只能放一次。 2.分

系统管理员/ 2022年09月10日 11:27/ 0 赞/ 220 阅读

相关背包问题-背包01-苹果

package 动态规划.背包01; import java.util.Scanner; public class 苹果 \{ static class

野性酷女/ 2022年07月12日 12:12/ 0 赞/ 259 阅读

相关 01背包问题

![Center][] ![Center 1][] [Center]: /images/20220616/e1a67e5ed0214bac8ec5293bc2b54

╰+攻爆jí腚メ/ 2022年06月16日 14:46/ 0 赞/ 237 阅读

相关 01背包问题

public class package0_1 { int V[][] = new int[200][200];//物品选取，背包承重 int max(

约定不等于承诺〃/ 2022年06月08日 06:15/ 0 赞/ 244 阅读

相关 01背包问题

【例9.11】01背包问题时间限制: 1000 ms 内存限制: 65536 KB 【题目描述】一个旅行者有一个最多能装M公斤的背包，现在有n件物

淩亂°似流年/ 2022年06月08日 03:59/ 0 赞/ 239 阅读

相关背包问题—01背包、完全背包

01背包问题题目有m件物品和一个容量为V 的背包。放入第i 件物品占用的体积是Vi，得到的价值是Wi。求解将哪些物品装入背包可使价值总和最大。思路这

末蓝、/ 2022年05月30日 10:10/ 0 赞/ 369 阅读

相关 01背包问题

简单背包问题设有一个背包可以放入的物品重量为S，现有n件物品，重量分别是w1，w2，w3，…wn。问能否从这n件物品中选择若干件放入背包中，使得放入的重量之和正好为S

痛定思痛。/ 2022年05月26日 12:18/ 0 赞/ 237 阅读

相关 01背包问题

转载：[https://blog.csdn.net/xp731574722/article/details/70766804][https_blog.csdn.net_xp73

怼烎@/ 2022年05月06日 15:00/ 0 赞/ 292 阅读

相关背包问题01

题目有N件物品和一个容量为V的背包。第i件物品的费用是c\[i\]，价值是w\[i\]。求解将哪些物品装入背包可使价值总和最大。基本思路这是最基础的背包问题，特

左手的ㄟ右手/ 2022年01月29日 11:34/ 0 赞/ 329 阅读