即日起在codingBlog上分享您的技术经验即可获得积分,积分可兑换现金哦。

贪心算法–背包相关疑难问题

编程语言 qq_32688731 11℃ 0评论
本文目录
[隐藏]

1. 背包问题

时间限制:3000 ms  |  内存限制:65535 KB
难度:3
描述
现在有很多物品(它们是可以分割的),我们知道它们每个物品的单位重量的价值v和重量w(1<=v,w<=10);如果给你一个背包它能容纳的重量为m(10<=m<=20),你所要做的就是把物品装到背包里,使背包里的物品的价值总和最大。
输入
第一行输入一个正整数n(1<=n<=5),表示有n组测试数据;


随后有n测试数据,每组测试数据的第一行有两个正整数s,m(1<=s<=10);s表示有s个物品。接下来的s行每行有两个正整数v,w。
输出
输出每组测试数据中背包内的物品的价值和,每次输出占一行。
样例输入
1
3 15
5 10
2 8
3 9
样例输出
65


背包问题,我靠,以为是dp结果发现想多了,代码也写复杂了。

import java.util.Scanner;

public class T1背包问题 {

 public static void main(String[] args) {
 
  Scanner sc=new Scanner(System.in);
  while(sc.hasNext()){
   int n=sc.nextInt();
   int[] out=new int[n];
   for (int i = 0; i < out.length; i++) {
    int s=sc.nextInt();
    int m=sc.nextInt();
    int[][] data=new int[s][2];
    for (int j = 0; j < data.length; j++) {
     data[j][0]=sc.nextInt();
     data[j][1]=sc.nextInt();
    }
    data=sort(data);
    int sum=0;
    for (int j = 0; j < data.length; j++) {
     if(m>0){
      if(m>=data[j][1]){
       sum+=data[j][0]*data[j][1];
       m-=data[j][1];
      }else{
       sum+=data[j][0]*m;
       break;
      }
     }
    }
    out[i]=sum;
   }
   for (int i = 0; i < out.length; i++) {
    System.out.println(out[i]);
   }
  }
 }

 private static int[][] sort(int[][] data) {
  
  int a,b;
  for (int i = 0; i < data.length; i++) {
   for (int j = i+1; j < data.length; j++) {
    if(data[i][0]





转载请注明:CodingBlog » 贪心算法–背包相关疑难问题

喜欢 (0)or分享 (0)
发表我的评论
取消评论

*

表情