首页 > 代码库 > 01背包--动态规划
01背包--动态规划
https://i.cnblogs.com/EditPosts.aspx?opt=1
这里主要是想改进一下二维数组的做法，用一维数组来实现01背包，也叫做滚动数组！
先借用某位大牛的一句话：“01背包在二维数组上操作，就是为了防止一个物品被放入多次的情况“
但其实01背包也可以用一维数组来做啦！
这里是把状态只用一维数组来表示，dp[j]表示放到第j个物品（或者说是前j个物品）的时候的最大价值，少了一维，感觉好神奇...不过在我仅仅做过的题目中，好像有很多都是用滚动数组的形式...
好了，用回当年的辣个栗子：
----------------------------------------
让我假设现在的背包的容量是C=10；
物品编号： 1 2 3
物品重量： 5 6 4
物品价值：20 10 12
---------------------------------------
直接分析dp数组：
dp：0 0 0 0 0 0 0 0 0 0
i=1:
dp[10] = max(dp[5]+20, dp[10]);
dp[9] = max(dp[4]+20, dp[9]);
dp[8] = max(dp[3]+20, dp[8]);
dp[7] = max(dp[2]+20, dp[7]);
dp[6] = max(dp[1]+20, dp[6]);
dp[5] = max(dp[0]+20, dp[5]);
dp: 0 0 0 0 20 20 20 20 20 20
---------------------------------------------
i=2:
dp[10] = max(dp[6]+4, dp[10]);
dp[9] = max(dp[3]+10, dp[9]);
dp[8] = max(dp[2]+10, dp[8]);
dp[7] = max(dp[1]+10, dp[7]);
dp[6] = max(dp[0]+10, dp[6]);
dp: 0 0 0 0 20 20 20 20 20 20 //看到了没，选10的都被之前的20压下去了
-------------------------------------------
i=3:
dp[10] = max(dp[6]+12, dp[10]);
dp[9] = max(dp[5]+12, dp[9]);
dp[8] = max(dp[4]+12, dp[8]);
dp[7] = max(dp[3]+12, dp[7]);
dp[6] = max(dp[2]+12, dp[6]);
dp[5] = max(dp[1]+12, dp[5]);
dp[4] = max(dp[0]+12, dp[4]);
dp: 0 0 0 12 20 20 20 20 32 32
Hiho
输入
每个测试点（输入文件）有且仅有一组测试数据。
每组测试数据的第一行为两个正整数N和M,表示奖品的个数，以及小Ho手中的奖券数。
接下来的n行描述每一行描述一个奖品，其中第i行为两个整数need(i)和value(i)，意义如前文所述。
测试数据保证
对于100%的数据，N的值不超过500，M的值不超过10^5
对于100%的数据，need(i)不超过2*10^5, value(i)不超过10^3
输出
对于每组测试数据，输出一个整数Ans，表示小Ho可以获得的总喜好值。
样例输入
5 1000 144 990 487 436 210 673 567 58 1056 897
样例输出
2099
import java.util.*;
public class Main {
public static void main(String[] args)
{
//用一维数组实现
Scanner sc=new Scanner(System.in);
int n,m;
n=sc.nextInt();
m=sc.nextInt();
int need[] =new int[n];
int val[]=new int[n];
int f[]=new int[m+1];
for(int i=0;i<n;i++)
{
need[i]=sc.nextInt();
val[i]=sc.nextInt();
}
for(int i=0;i<n;i++)
{
for(int j=m;j>=need[i];j--)
{
f[j]=Math.max(f[j],f[j-need[i]]+val[i]);
}
}
System.out.println(f[m]);
}
}
01背包--动态规划