簡単なリュックサックの問題
3900 ワード
簡単なリュックサックの問題
1000(ms)
65535(kb)
1438/6830
Tags:検索[Tags:けんさく]
リュックサックを入れることができるものの重さはSで、既存のn個のものがあり、重さはそれぞれw 1,w 2,w 3,...wnである.
このn品の中からリュックサックに入れるものをいくつか選び、入れる重さの和がちょうどSになるようにしてもらえませんか.
条件を満たす選択がある場合は、このリュックサックには解があります.そうしないと、このリュックサックの問題は解がありません.
入力
サンプル出力
1000(ms)
65535(kb)
1438/6830
Tags:検索[Tags:けんさく]
リュックサックを入れることができるものの重さはSで、既存のn個のものがあり、重さはそれぞれw 1,w 2,w 3,...wnである.
このn品の中からリュックサックに入れるものをいくつか選び、入れる重さの和がちょうどSになるようにしてもらえませんか.
条件を満たす選択がある場合は、このリュックサックには解があります.そうしないと、このリュックサックの問題は解がありません.
入力
输入数据有多行,包括放入的物品重量为s,物品的件数n,以及每件物品的重量(输入数据均为正整数)
多组测试数据。
输出
对于每个测试实例,若满足条件则输出“YES”,若不满足则输出“NO“
样例输入
20 5
1 3 5 7 9
サンプル出力
YES
//#include
//#include
//using namespace std;
//
//main()
//{
// char *c1 = "abc";
//
// printf("%d %d %c %d %s
",&c1,c1,*c1,*c1,c1);
//
// getchar();
//}
#include
#include
#include
#include
#include
#include
#include
using namespace std;
int a[100],visit[100],k=0,wi,n;;
void def(int sum){
if(sum==wi)
k=1;
else{
for(int i=0;i>wi>>n){
for(int i=0;i>a[i];
k=0;
def(0);
if(k==1)
cout<