src/nowCoderClass1/section12/Backpack.java · TonyLee/Algorithm

代码拉取完成,页面将自动刷新

richgiteeai

Watch

不关注关注所有动态仅关注版本发行动态关注但不提醒动态

1 Star 0 Fork 2

TonyLee/Algorithm

forked from wangjili/Algorithm

代码 Issues 0 Pull Requests 0 Wiki 统计流水线

服务

加入 Gitee

与超过 1400万开发者一起发现、参与优秀开源项目,私有仓库也完全免费 :)

免费加入

已有帐号? 立即登录

文件

master

分支 (1)

管理

master

该仓库未声明开源许可证文件(LICENSE),使用请关注具体项目描述及其代码上游依赖。

项目仓库所选许可证以仓库主分支所使用许可证为准

克隆/下载

HTTPS SSH SVN SVN+SSH 下载ZIP

提示

下载代码请复制以下命令到终端执行

为确保你提交的代码身份被 Gitee 正确识别,请执行以下命令完成配置

git config --global user.name userName 
git config --global user.email userEmail

初次使用 SSH 协议进行代码克隆、推送等操作时,需按下述提示完成 SSH 配置

1 生成 RSA 密钥

2 获取 RSA 公钥内容,并配置到 SSH公钥中

在 Gitee 上使用 SVN,请访问使用指南

使用 HTTPS 协议时,命令行会出现如下账号密码验证步骤。基于安全考虑,Gitee 建议配置并使用私人令牌替代登录密码进行克隆、推送等操作

Username for 'https://gitee.com': userName

Password for 'https://userName@gitee.com': # 私人令牌

分支 1

标签 0

Algorithm

src

nowCoderClass1

section12

Backpack.java

Backpack.java 1.89 KB

package nowCoderClass1.section12;

/**
 * Created by Dell on 2017年06月05日.
 */
public class Backpack {
// public int maxValue(int[] w, int[] v, int n, int cap) {
// //下标表示前面的物品,
// int[] dp=new int[n+1];//存放i-1件物品的最大价值
// for(int i=1;i<=n;i++){
// int value=w[i-1]*v[i-1];
// if(value<cap){
// //比较放入该物品的价值,不放入该物品的价值
// int yes=value+dp[i-1];
// int no=dp[i-1];
// dp[i]=yes
// }
// }
// }
// public int maxValue(int[] w, int[] v, int n, int cap) {
// // dp[x][y]表示物品数量为x,重量不超过y时背包中的总价值
// //两种情况:1.将x物品不加入到背包中,那么前x-1件物品的总重量不应该超过y。dp[x][y] = dp[x-1][y]
// //2.将x物品加入到背包中,那么前x-1前物品的总重量不应该超过y-w(x),因此dp[x][y] = dp[x-1][y-w(x)]+v(x);
// int[] dp = new int[cap+1];
//
// for(int i=0;i<n;i++){//控制物品的数量
// for(int j=cap;j>=w[i];j--){//空背包中不能超重
// dp[j] = dp[j]>=dp[j-w[i]]+v[i]?dp[j]:dp[j-w[i]]+v[i];//选取j加入书包与j不加入书包的较大值
// }
// }
//
// return dp[cap];//返回数组的最后一位即是最大总价值
// }
 public int maxValue(int[] w, int[] v, int n, int cap) {
 int[] dp=new int[cap+1];//用cap+1是要存储重量为0时的价值,避免越界
 for(int i=0;i<n;i++){
 //思考为什么是从后往前,而不是从前往后呢
 //如果从前往后计算,可能会将一件物品的价值重复加入最大价值中
 for(int j=cap;j>=w[i];j--){
 dp[j]=dp[j]>dp[j-w[i]]+v[i]?dp[j]:dp[j-w[i]]+v[i];
 }
 }
 return dp[cap];
 }

}

一键复制编辑原始数据按行查看历史

RosinaWang 提交于 2017年09月05日 17:20 +08:00 . first commit

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46

package nowCoderClass1.section12;

/**
 * Created by Dell on 2017年06月05日.
 */
public class Backpack {
// public int maxValue(int[] w, int[] v, int n, int cap) {
// //下标表示前面的物品,
// int[] dp=new int[n+1];//存放i-1件物品的最大价值
// for(int i=1;i<=n;i++){
// int value=w[i-1]*v[i-1];
// if(value<cap){
// //比较放入该物品的价值,不放入该物品的价值
// int yes=value+dp[i-1];
// int no=dp[i-1];
// dp[i]=yes
// }
// }
// }
// public int maxValue(int[] w, int[] v, int n, int cap) {
// // dp[x][y]表示物品数量为x,重量不超过y时背包中的总价值
// //两种情况:1.将x物品不加入到背包中,那么前x-1件物品的总重量不应该超过y。dp[x][y] = dp[x-1][y]
// //2.将x物品加入到背包中,那么前x-1前物品的总重量不应该超过y-w(x),因此dp[x][y] = dp[x-1][y-w(x)]+v(x);
// int[] dp = new int[cap+1];
//
// for(int i=0;i<n;i++){//控制物品的数量
// for(int j=cap;j>=w[i];j--){//空背包中不能超重
// dp[j] = dp[j]>=dp[j-w[i]]+v[i]?dp[j]:dp[j-w[i]]+v[i];//选取j加入书包与j不加入书包的较大值
// }
// }
//
// return dp[cap];//返回数组的最后一位即是最大总价值
// }
 public int maxValue(int[] w, int[] v, int n, int cap) {
 int[] dp=new int[cap+1];//用cap+1是要存储重量为0时的价值,避免越界
 for(int i=0;i<n;i++){
 //思考为什么是从后往前,而不是从前往后呢
 //如果从前往后计算,可能会将一件物品的价值重复加入最大价值中
 for(int j=cap;j>=w[i];j--){
 dp[j]=dp[j]>dp[j-w[i]]+v[i]?dp[j]:dp[j-w[i]]+v[i];
 }
 }
 return dp[cap];
 }

}