题目描述 有一个箱子容量为V（正整数，），同时有n个物品（），每个物品有一个体积（正整数）。 要求n个物品中，任取若干个装入箱内，使箱子的剩余空间为最小。 输入描述: 1个整数，表示箱子容量 1个整数，表示有n个物品 接下来n行，分别表示这n个物品的各自
展开全文
Thinking Process
1、先确定状态
f[i][j]:前i个物体能不能装满体积为j的背包?
则现在有两个选择：
选第i个物体：要看一下f[i-1][j-c[i]]，它能装下，那这个决定就可以装下
不选第i个物体：要看一下f[i-1][j]
故推出状态方程：
f[i][j] = f[i
展开全文
总结：本题使用动态规划
import java.util.*;
public class Main{
public static void main(String arg[]){
Scanner sc = new Scanner(System.in);
int
展开全文
#include<bits/stdc++.h>
using namespace std;
int main()
{
int n;
int v;
cin >> v;
cin >> n;//dp[v]的意思为：容量为v时，能装的最大体积
展开全文
解法：
01背包 dp
为什么可以用01背包来解？
当我开始思考这道题的时候，首先排除的01背包，一方面感觉V太大，另一方面是存在一个误解：最后得出的最大值有可能超过箱子的容量。
实则不然，当物品的价值等于物品的大小时，计算dp[i][j]的过程中，j（容量）一直限制dp[i][j]的大小，dp[i
展开全文
0-1背包的变型dp[i][j]表示考虑了前i个物品，当背包大小为j的时候，剩余的最少空间。初始化：起初一个物品都没有放入，所以dp[0][j] = j；转移方程：if (a[i] < j) dp[i][j] = min(dp[i - 1][j], dp[j - a[i]]);else dp[
展开全文
#include <stdio.h>
#include <string.h>
int max(int a, int b) {
if (a >= b ) {
return a;
}
return b;
}
int main() {
展开全文
import java.util.*;
public class Main {
public static void main(String[] args) {
Scanner scan = new Scanner(System.in);
int V = In
展开全文
滚地数组
#include <iostream>
using namespace std;
int a[40];
int f[20020]; //数组滚动
int n, v;
int main(){
cin >> v >> n;
for(int
展开全文
#include <stdio.h>
int max(int a,int b)
{
return a>b?a:b;
}
int arr[31];
int val[200001];
int main() {
int v,n;
scanf("%d%d
展开全文
-
扫描二维码，关注牛客
- 意见反馈
-
下载牛客APP，随时随地刷题
- 牛客竞赛，专业的竞技算法训练平台
-
扫描二维码，进入QQ群
扫码关注“比赛自动姬”
- 公司地址：北京市朝阳区北苑路北美国际商务中心K1座一层-北京牛客科技有限公司
- 联系方式：010-60728802 投诉举报电话：010-57596212（朝阳人力社保局）
- 牛客科技© All rights reserved admin@nowcoder.com
- 京ICP备14055008号-4 增值电信业务经营许可证 营业执照 人力资源服务许可证
-
京公网安备 11010502036488号
