程序師世界是廣大編程愛好者互助、分享、學習的平台,程序師世界有你更精彩!
首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫知識
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
 程式師世界 >> 編程語言 >> C語言 >> C++ >> C++入門知識 >> Uva 642-CD(0-1背包+打印路徑)

Uva 642-CD(0-1背包+打印路徑)

編輯:C++入門知識

Uva 642-CD(0-1背包+打印路徑)


題目鏈接:點擊打開鏈接

裸01背包 ,此題中 價值即體積... 打印路徑。。不多說了 一維的沒看懂。。上個二維的

#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#define maxn 10100
#define _ll __int64
#define ll long long
#define INF 0x3f3f3f3f
#define Mod 1000000007
#define pp pair
#define ull unsigned long long
using namespace std;
int N,n,w[25],dp[25][maxn],ans[25];
void input()
{
	memset(dp,0,sizeof(dp));
	for(int i=1;i<=n;i++)
	{
		scanf("%d",&w[i]);
		for(int j=0;j<=N;j++)
		{
			dp[i][j]=(i==1?0:dp[i-1][j]);
		    if(j>=w[i])dp[i][j]=max(dp[i-1][j],dp[i-1][j-w[i]]+w[i]);
		}
	}
}
void output()
{
	int p=0,c=dp[n][N];
	for(int i=n;i>=1;i--)
	{
		if(dp[i][c]!=dp[i-1][c])
		{
			ans[p++]=i;
			c-=w[i];
		}
	}
	for(int i=p-1;i>=0;i--)
		printf("%d ",w[ans[i]]);
	printf("sum:%d\n",dp[n][N]);
}
int main()
{
	while(scanf("%d %d",&N,&n)!=EOF)
	{

		input();
		output();
	}
    return 0;
}


  1. 上一頁:
  2. 下一頁:
Copyright © 程式師世界 All Rights Reserved