一亩三分地

 找回密码 注册账号

扫描二维码登录本站

BBS
指尖新闻
Offer多多
Salarytics
Learn
Who's Hiring?
疫情动态
Instant
客户端
微信公众号
扫码关注公众号
留学申请公众号
扫码关注留学申请公众号
Youtube频道
留学博客
关于我们
查看: 331|回复: 0
收起左侧

[动态规划] 动态规划DP系列 -分组背包问题

[复制链接] |试试Instant~ |刷题, 动态规划
我的人缘0

分享帖子到朋友圈
本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   91% (11)
 
 
8% (1)    👎

注册一亩三分地论坛,查看更多干货!

您需要 登录 才可以下载或查看,没有帐号?注册账号

x
有 N 组物品和一个容量是 V 的背包。

每组物品有若干个,同一组内的物品最多只能选一个。
每件物品的体积是 vij,价值是 wij,其中 i 是组号,j 是组内编号。

求解将哪些物品装入背包,可使物品总体积不超过背包容量,且总价值最大。

输出最大价值。

输入格式
第一行有两个整数 N,V,用空格隔开,分别表示物品组数和背包容量。

接下来有 N 组数据:

每组数据第一行有一个整数 Si,表示第 i 个物品组的物品数量;
每组数据接下来有 Si 行,每行有两个整数 vij,wij,用空格隔开,分别表示第 i 个物品组的第 j 个物品的体积和价值;
输出格式
输出一个整数,表示最大价值。

数据范围
0<N,V≤100
0<Si≤100
0<vij,wij≤100
输入样例
3 5
2
1 2
2 4
1
3 4
1
4 5
输出样例:
8



import java.util.Scanner;
import java.util.ArrayList;
import java.util.List;
import java.util.NoSuchElementException;
public class Main{
    public static void main(String[] args) throws Exception {
        // 读入数据的代码
        Scanner reader = new Scanner(System.in);
        // 物品的数量为N
        int N = reader.nextInt();
        // 背包的容量为V
        int V = reader.nextInt();
        List<int [][]> groups = new ArrayList<>();
        while(true){
            int  groupSize = 0;
            try{
            groupSize = reader.nextInt();

            }catch(NoSuchElementException e){
                break;

            }
       int [][] group= new int[groupSize][2];
       groups.add(group);
       for(int i=0;i<groupSize;i+=1){

                  group[i][0] = reader.nextInt();
                  group[i][1] = reader.nextInt();
           }
        }
       reader.close();
       int [] dp = new int[V+1];
       int numberOfGroup = groups.size();
       for(int i=0;i<numberOfGroup;i+=1){
           for(int j=V;j>0;j-=1){
               int [][] group = groups.get(i);
               int groupSize = group.length;
               for(int k=0;k<groupSize;k+=1){

                   if(j>=group[k][0]){
                       dp[j] = Math.max(dp[j],  dp[j-group[k][0]]+group[k][1]);
                   }

               }
           }
       }
       System.out.println(dp[V]);

    }
}





上一篇:动态规划DP系列 -二维费用的背包问题
下一篇:动态规划DP系列 -背包问题求方案数
您需要登录后才可以回帖 登录 | 注册账号

本版积分规则

隐私提醒:
■为防止被骚扰甚至人肉,不要公开留微信等联系方式,请以论坛私信方式发送。
■特定版块可以超级匿名:https://pay.1point3acres.com/tools/thread
■其他版块匿名方法:http://www.1point3acres.com/bbs/thread-405991-1-1.html

手机版|||一亩三分地

GMT+8, 2020-5-28 05:41

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

快速回复 返回顶部 返回列表