题解 | #Knapsack Problem#

传送门->https://ac.nowcoder.com/acm/problem/13882

题意翻译

题目描述

今天，HH 成为一名购物者，他想买很多东西。 HH有一个包最多可以装w公斤的东西，他有d美元。 现在他想买 n 件物品，第 i件物品重量 w i公斤，花费 c i美元。 H他不擅长数学，所以他让你告诉他是否可以买所有东西并随身携带。

输入输出

第一行包含一个正整数T(1≤T≤10)，表示有T个测试用例。 对于每个测试用例： 第一行包含三个正整数n,w,d(1≤n≤100,1≤w≤100,1≤d≤100)——HH想要购买的物品数量，他的包可以携带的最大重量，和他有的钱。 第二行包含 n 个整数 w 1 ,w 2 …w n (1≤w i ≤100)。第三行包含 n 个整数 c 1 ,c 2 …c n (1≤c i ≤100)。

对于每个测试用例，如果 HH 可以购买所有物品并将它们放在他的包中，则输出一行“YES”（不带引号），否则输出“NO”（不带引号）。

样例

2

4 12 17

1 2 4 5

5 4 6 2

4 11 17

1 2 4 5

5 4 6 2

YES

NO

说明

在第一个例子中，所有物品总共花费 17 美元，总共重 12 公斤，HH 有足够的钱，他的包可以装 12 公斤的东西。

最简单的做法是

把物品的重量和价格分别求和，在和背包的重量和手里的money作比较。

上代码

  #include<iostream>
  using namespace std;
  //主程序
  int main()
  {
      int T,n,w,d;
      int ww[105],c[105];//ww是重量数组，c是价格数组
      cin>>T;
      while(T--){
          int sumw=0,sumc=0;//一定要赋值为0！！！
          cin>>n>>w>>d;
          for(int i=1;i<=n;i++){
              cin>>ww[i];
              sumw+=ww[i];
          }
          for(int i=1;i<=n;i++){
              cin>>c[i];
              sumc+=c[i];
          }
          /*
          	if物品的总重量和总价格都小于HH背包的耐久和手中的money,输出YES
            else 输出NO
   		  */
         
          if(sumw<=w&&sumc<=d)
              cout<<"YES";
          else
              cout<<"NO";
          puts("");//等于 cout<<endl;	
      }
      return 0;
  }