呀呀了个呸的

用户名：uq_36086153189

访问量：282

签　名：

等　　级
排　　名	57167
经　　验	240
参赛次数	0
文章发表	1
年　　龄	0
在职情况	学生
学　　校
专　　业

　　自我简介：

TA的其他文章

dp01背包问题
浏览：102

你可能喜欢

C语言程序设计教程（第三版）课后习题6.10 （C语言代码）

C语言训练-求具有abcd=(ab+cd)2性质的四位数（C语言代码）

C语言程序设计教程（第三版）课后习题6.11 （C语言代码）

dp01背包问题

　　作者: 呀呀了个呸的　　　　发表时间：2022-04-08 20:48:50 浏览：102　|　评论：0　

原题链接：信息学奥赛一本通T1267-01背包问题

```
import java.util.Scanner;

public class Main {
	public static void main(String[] args) {
		Scanner scan = new Scanner(System.in);
        //在此输入您的代码...
		int m = scan.nextInt();
		int n = scan.nextInt();
		int []wight = new int[n+1];
		int []value = new int[n+1];
		
		for(int i=1; i<=n; i++) {
			wight[i] = scan.nextInt();
			value[i] = scan.nextInt();
		}
		int ans;
		//ans = dpFun(wight, value, m); // 二维dp
		ans = dpFun2(wight, value, m);  // 一维dp
		System.out.println(ans);
        scan.close();
	}
	
	static int dpFun(int wight[], int value[], int m) {
		int n = value.length-1;
		int [][]dp = new int[n+1][m+1];
		for(int i=1; i<=n; i++) {
			for(int j=1; j<=m; j++) {
				if(wight[i] > j) 
					dp[i][j] = dp[i-1][j];
				if(wight[i] <= j)
					dp[i][j] = Math.max(dp[i-1][j], dp[i-1][j-wight[i]]+value[i]);
			}
		}
		return dp[n][m];
	}
	
	static int dpFun2(int wight[], int value[], int m) {
		int n = value.length-1;
		int []dp = new int[m+1];
		for(int i=1; i<=n; i++) {
			for(int j=m; j>=0; j--) {
				if(j >= wight[i])
					dp[j] = Math.max(dp[j], dp[j-wight[i]]+value[i]);
			}
		}
		return dp[m];
	}
}
```

0.0分

0 人评分

看不懂代码解释一下代码? 或者生成一段代码？试试AI编程助手吧

呀呀了个呸的

TA的其他文章

你可能喜欢

C语言程序设计教程（第三版）课后习题6.10 （C语言代码）

C二级辅导-进制转换（C语言代码）

C语言训练-求具有abcd=(ab+cd)2性质的四位数（C语言代码）

C语言程序设计教程（第三版）课后习题6.11 （C语言代码）

C语言程序设计教程（第三版）课后习题1.5 （C语言代码）

dp01背包问题

评论区

精彩推荐

C二级辅导-进制转换（C语言代码）

A+B for Input-Output Practice (IV) （C++代码）

回文数(一) （C语言代码）

C语言程序设计教程（第三版）课后习题10.3 （C语言代码）

DNA （C语言代码）

C语言程序设计教程（第三版）课后习题9.4 （C语言代码）

C语言程序设计教程（第三版）课后习题3.7 （C语言代码）

小九九（C语言描述,不看要求真坑爹）

C语言程序设计教程（第三版）课后习题8.6 （C语言代码）

简单的a+b （C语言代码）

呀呀了个呸的

TA的其他文章

你可能喜欢

C语言程序设计教程（第三版）课后习题6.10 （C语言代码）

C二级辅导-进制转换 （C语言代码）

C语言训练-求具有abcd=(ab+cd)2性质的四位数 （C语言代码）

C语言程序设计教程（第三版）课后习题6.11 （C语言代码）

C语言程序设计教程（第三版）课后习题1.5 （C语言代码）

dp01背包问题

评论区

精彩推荐

C二级辅导-进制转换 （C语言代码）

A+B for Input-Output Practice (IV) （C++代码）

回文数(一) （C语言代码）

C语言程序设计教程（第三版）课后习题10.3 （C语言代码）

DNA （C语言代码）

C语言程序设计教程（第三版）课后习题9.4 （C语言代码）

C语言程序设计教程（第三版）课后习题3.7 （C语言代码）

小九九 （C语言描述,不看要求真坑爹）

C语言程序设计教程（第三版）课后习题8.6 （C语言代码）

简单的a+b （C语言代码）

C二级辅导-进制转换（C语言代码）

C语言训练-求具有abcd=(ab+cd)2性质的四位数（C语言代码）

　　评论区

C二级辅导-进制转换（C语言代码）

小九九（C语言描述,不看要求真坑爹）