这里大雪菜讲的那个我想来想去,虽然理解了(大雾),但是写成Java代码的时候,永远accept不了,
我想应该还有同学跟我一样,对大雪菜说的方法懵懵懂懂的
后来我想了想,比较容易理解的还是从第N种物品倒推。即对于第i件物品,当满足条件volumn_left >= v[i] && dp[i][volumn_left] == (dp[i-1][volumn_left-v[i]] + w[i])
时,认为我们一定选择了该种物品(即第i种物品),然后去看第i - 1 种物品有没有被选上。
但是这样有一个问题,OJ判断要求字典序最小,我这样的不一定啊,可能存在两种方案,例如 1 +2 和5 + 4,我这里选出来的是第二种,emmmm,怎么办呢,
答:输入的时候把输入逆序就好了嘛,然后提供一个记录物品序号的数组index,这样就可以了。
emmm,说的可能不是很清楚,等我整理一下再来改改。
要点在于这两个地方:
for (int i = N; i >= 1; i--) {
v[i] = input.nextInt();
w[i] = input.nextInt();
index[i] = ++index_temp;
}
和
ArrayList<Integer> ans = new ArrayList<>();
// 这里开始反推方案
int volumn_left = V;
for(int i = N; i >= 1; i--){
if(volumn_left >= v[i] && dp[i][volumn_left] == (dp[i-1][volumn_left-v[i]] + w[i])){
// 说明选择了当前物品
ans.add(Integer.valueOf(index[i]));
// 背包减去当前物品的体积
volumn_left -= v[i];
}
if(volumn_left <= 0){
break;
}
}
return ans;
全文代码如下,成功AC
import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;
public class Main{
public static void main(String[] args) {
// N个物品
int N;
// 背包体积
int V;
// 每个物品的体积
int[] v;
// 每一个物品的价值
int[] w;
//代表物品的输入index
int[] index;
// start input
Scanner input = new Scanner(System.in);
N = input.nextInt();
V = input.nextInt();
v = new int[N + 1];
w = new int[N + 1];
index = new int[N + 1];
int index_temp = 0;
for (int i = N; i >= 1; i--) {
v[i] = input.nextInt();
w[i] = input.nextInt();
index[i] = ++index_temp;
}
input.close();
// start solution
Main solution = new Main();
List<Integer> ans = solution.solution_scheme(N,V,v,w, index);
for(int i = 0; i < ans.size() -1; i++){
System.out.print(ans.get(i));
System.out.print(" ");
}
System.out.print(ans.get(ans.size() -1));
}
public List<Integer> solution_scheme(int N, int V, int[] v, int[] w, int[] index){
// 首先标准的01问题解决方案,这里用原始方法求解,即dp矩阵是二维的
int[][] dp = new int[N+1][V+1];
for(int i = 1; i <= N; i++){
for(int j = 0; j <= V; j++){
if(j >= v[i]){
dp[i][j] = Math.max(dp[i-1][j], dp[i-1][j-v[i]] + w[i]);
}else {
dp[i][j] = dp[i-1][j];
}
}
}
ArrayList<Integer> ans = new ArrayList<>();
// 这里开始反推方案
int volumn_left = V;
for(int i = N; i >= 1; i--){
if(volumn_left >= v[i] && dp[i][volumn_left] == (dp[i-1][volumn_left-v[i]] + w[i])){
// 说明选择了当前物品
ans.add(Integer.valueOf(index[i]));
// 背包减去当前物品的体积
volumn_left -= v[i];
}
if(volumn_left <= 0){
break;
}
}
return ans;
}
}
终于让我找到了,我就觉得应该有一样的想法hh
nb
nb
只能用两个字评价:NB